답안 #290757

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
290757	2020-09-04T12:21:19 Z	PKhing	Bigger segments (IZhO19_segments)	C++14	0 / 100	1 ms	384 KB

segments

#include<bits/stdc++.h>
#define ll long long
#define ii pair<ll,ll>
using namespace std;
ll tab[500005];
ll qs[500005];
ll dp[500005];
ll dp2[500005];
int n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&tab[i]);
        qs[i]=tab[i]+qs[i-1];
    }
    set<ii,greater<ii>> s;
    s.insert(make_pair(0,0));
    for(int i=1;i<=n;i++){
        auto x = s.lower_bound(make_pair(qs[i],1e9));
        ll want = 2*qs[i]-qs[x->second];
        dp[i] = dp[x->second]+1;
        queue<ii> del;
        for(auto i:s){
            if(i.second>=want){
                del.emplace(i);
            }
            else break;
        }
        while(!del.empty()){
            s.erase(del.front());
            del.pop();
        }
        s.insert(make_pair(want,i));
    }
    printf("%lld",dp[n]);

}

Compilation message

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

Subtask #1

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 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	0 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Incorrect	0 ms	384 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #2

0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 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	0 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Incorrect	0 ms	384 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #3

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 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	0 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Incorrect	0 ms	384 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #4

0 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 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	0 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Incorrect	0 ms	384 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #5

0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 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	0 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Incorrect	0 ms	384 KB	Output isn't correct
11	Halted	0 ms	0 KB	-