oj.uz

Submission #299750

# Submission time Handle Problem Language Result Execution time Memory
299750 2020-09-15T14:57:33 Z dantoh000 Bigger segments (IZhO19_segments) C++14
0 / 100
 1 ms 384 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll, int> li;
ii dp[500005];
int n;
ll p[500005];
ll k[500005];
priority_queue<li, vector<li>, greater<li> > pq;
int main(){
    scanf("%d",&n);
    pq.push({0,0});
    for (int i = 1; i <= n; i++){
        scanf("%lld",&p[i]);
        p[i]+=p[i-1];
        dp[i] = {0,0};
        li cur;
        while (pq.size() && pq.top().fi <= p[i]){
            cur = pq.top(); pq.pop();
        }
        pq.push(cur);
        int j = cur.se;
        if (p[i] >= k[j]){
            dp[i] = {dp[j].fi+1, j};
            k[i] = 2*p[i]-p[j];
            //printf("%lld: ",2*p[i]-p[j]);
            pq.push({k[i],i});
        }
    }
    printf("%d",dp[n].fi);
}

Compilation message

segments.cpp: In function 'int main()':
segments.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   14 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
segments.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |         scanf("%lld",&p[i]);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Incorrect 1 ms 384 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Incorrect 1 ms 384 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Incorrect 1 ms 384 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Incorrect 1 ms 384 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Incorrect 1 ms 384 KB Output isn't correct
11 Halted 0 ms 0 KB -