I couldn't get AC on problem C. Now reading the AC solution I get it. I didn't understand the problem statement (I thought I did).

I bet that the vast majority that got AC and not WA on problem C were reading the japanese problem statement.

using dp
solution here

I somehow find the pattern, but I can't prove it.

I could not solve it but we need to do it in O(n^2).

Let $$$dp[i][j]$$$ show the number of pairs using the first i elements of the first array and the first j elements of the second array. Then, the first thing to write is, $$$dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]$$$. We subtract $$$dp[i-1][j-1]$$$ because it was counted twice. That's the case when we don't use $$$a_i$$$ and $$$b_j$$$ in some pair. If we use them, as they are the last elements, they must be equal, and that would contribute the answer as $$$dp[i-1][j-1]$$$. So, if $$$a_i$$$ is equal to $$$b_j$$$, add $$$1+dp[i-1][j-1]$$$ to the $$$dp[i][j]$$$. And don't forget to add 1 as we need count the empty pair.

Code

There will be rank changes and Japanese editorial in a couple of minutes. Just wait

An "editorial" button will appear next to the "discuss" button on the contest page soon, I'm assuming that you are asking where you can see the rating change, rating change will appear on your atcoder profile after they update it if you are looking for you rank then you can press the standings button on the contest page. Usually, atcoder updates rating and adds editorial within an hour.

Notice that you can always divide the rectangle into two equal parts. If the point is in the middle of the rectangle, then there are infinitely many ways to do it. Otherwise, there is only one.

I guess the easiest solution is using two pointers. Iterate through the first pointer, and increase the second one such that the sum of the current segment is $$$<K$$$ and this subarray is the rightmost one. Then add the count of the numbers in the left as the sum from any of them to the current element would be $$$\geq K$$$. Code

Another solution would be a binary search.

We build the prefix-sum array s (s[i]=s[i-1]+a[i])

For each i, we find the lower_bound of s[i-1]+k (>=s[i-1]+k). As the subsequence from i to pos (the lower_pound) will have sum >=k (because s[pos]-s[i-1]?=k). Because all the elements are positive so s[i] always >= s[i-1] so if subsequence from i to pos (the lower_pound) satisfy the condition, subsequence from i to pos+1, pos+2,... n will also satisfy the condition. So with each i res+=n-pos;

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,a[100003];
ll k,s[100003],res=0;
int main()
{
    //freopen("D.inp","r",stdin);
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin >> n>>k;
    s[0]=0;
    for (int i=1;i<=n;i++) cin >> a[i],s[i]=s[i-1]+a[i];
    for (int i=1;i<=n;i++)
    {
        int pos=lower_bound(s+i,s+1+n,s[i-1]+k)-s;
        if (pos==n+1&&s[n]<s[i-1]+k) break;
        res+=n-pos+1;
    }
    cout << res;
}

【ABC130】
コンテストは終了しました。ご参加ありがとうございました。
解説PDF：https://t.co/0xYlmqUAWO
解説放送：https://t.co/FdyPH25nj6

— AtCoder (@atcoder) June 16, 2019

Bounding box area is a function which definitely has a minimum. Just check all bbxoes for time from 0 to 10^18 (could be less) with ternary search. All tests passed in less than second (will provide solution link later).

The reason why they don't give English editorials is because there isn't enough English-speaking participants in atcoder.

Either way, you can just google translate the editorial, and most problems (especially ABC) have code that is easy to understand, and if you need implementation from later problems, just look at top submissions. And also they added as "Discuss" tab which leads to this link, where english-speaking users can discuss the tasks.

Good day to you,

well every line that goes throug middle (meaning intersection of diagonals) cuts it into two same halves. As you can observe, from every point you can do so ;-)

You could also observe the behavour of area if you draw any line and the just rotate it ^_^

Good Luck :)

use arr instead of string

and take care when %q on L22

Good day to you,

well for example I solved it recursively ;-) Here is the code :)

Not sure whether it helps, yet good luck with parsing ;-)

Hi! , this is my recursive Solution

I may have followed many bad practices in the sol , so pls just focus on the giveans function instead :D

For N=1e5 O(N^2) would not pass. You can observe that all elements are positive so the prefix sum would be monotonic. Iterate over all value of right index then find maximum left index such that prefix[r]-prefix[l]>=k. This can be done in O(logn) using binary search. Final complexity would be O(nlogn). heres my submission. https://atcoder.jp/contests/abc130/submissions/5964123