Submission #467054

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
467054	2021-08-21 13:31:28	mosiashvililuka	Bigger segments (IZhO19_segments)	C++14	100 / 100	159 ms	48200 KiB

segments

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,dp[500009],dp2[500009],f[500009],jm[500009],lef,rig,mid;
vector <long long> v[500009];
int main(){
  ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  cin>>a;
  for(i=1; i<=a; i++){
    cin>>f[i];jm[i]=jm[i-1]+f[i];
  }
  for(i=1; i<=a; i++){
    dp[i]=1;dp2[i]=jm[i];
    for(vector <long long>::iterator it=v[i].begin(); it!=v[i].end(); it++){
      /*if(dp[i]<dp[(*it)]+1||(dp[i]==dp[(*it)]+1&&dp2[i]>jm[i]-jm[(*it)])){
        dp[i]=dp[(*it)]+1;dp2[i]=jm[i]-jm[(*it)];
      }*/
      jj=max((*it),jj);
    }
    if(jj!=0){
      if(dp[i]<dp[jj]+1||(dp[i]==dp[jj]+1&&dp2[i]>jm[i]-jm[jj])){
        dp[i]=dp[jj]+1;dp2[i]=jm[i]-jm[jj];
      }
    }
    /*for(j=i-1; j>=1; j--){
      if(dp2[j]+jm[j]<=jm[i]){
        dp[i]=dp[j]+1;dp2[i]=jm[i]-jm[j];
        break;
      }
    }*/
    lef=0;rig=a+1;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27