Submission #1225494

#TimeUsernameProblemLanguageResultExecution timeMemory
1225494salmonSparklers (JOI17_sparklers)C++20
30 / 100
0 ms328 KiB
#include <bits/stdc++.h> using namespace std; int N,K; long long int T; int lst[1100]; int main(){ scanf(" %d",&N); scanf(" %d",&K); scanf(" %lld",&T); for(int i = 1; i <= N; i++) scanf(" %d",&lst[i]); int s = 0; int e = 1e9; while(s != e){ int m = (s + e)/2; m *= 2; long long int cesh = T * m; int it = K - 1; int it1 = K + 1; pair<long long int, long long int> profeet = {0,0}; pair<long long int, long long int> profeet1 = {0,0}; bool one = false; while(it != 0 && (!one || profeet.first < 0) ){ one = true; profeet.first += T * m - (lst[it + 1] - lst[it]); profeet.second = min(profeet.second,profeet.first - T * m); it--; } one = false; while(it1 != N + 1 && (!one || profeet1.first < 0) ){ one = true; profeet1.first += T * m - (lst[it1] - lst[it1 - 1]); profeet1.second = min(profeet1.second,profeet1.first - T * m); it1++; } int l = K; int r = K; while(l != 1 && r != N && cesh < 2 * lst[N]){ /*printf("%d %d %lld\n",l,r,cesh); printf("%d %d\n",it,it1); printf("%lld %lld\n",profeet.first,profeet.second); printf("%d %d\n",profeet1.first,profeet1.second);*/ //printf("\n"); if(cesh >= -min(profeet.second, profeet1.second)){ if(max(profeet.first, profeet1.first) < 0){ long long int num = 0; if(profeet.second < profeet1.second){ while(num != profeet.second){ if(num == 0) num = lst[l - 1] - lst[l]; else num += T * m + lst[l - 1] - lst[l]; l--; } cesh += num + T * m; it = l - 1; one = false; profeet = {0,0}; while(it != 0 && (!one || profeet.first < 0) ){ one = true; profeet.first += T * m - (lst[it + 1] - lst[it]); profeet.second = min(profeet.second,profeet.first - T * m); it--; } } else{ while(num != profeet1.second){ if(num == 0) num = lst[r] - lst[r + 1]; else num += T * m + lst[r] - lst[r + 1]; r++; } cesh += num + T * m; it1 = r + 1; one = false; profeet1 = {0,0}; while(it1 != N + 1 && (!one || profeet1.first < 0) ){ one = true; profeet1.first += T * m - (lst[it1] - lst[it1 - 1]); profeet1.second = min(profeet1.second,profeet1.first - T * m); it1++; } } continue; } if(profeet.first > profeet1.first){ cesh += profeet.first; l = it + 1; one = false; profeet = {0,0}; while(it != 0 && (!one || profeet.first < 0) ){ one = true; profeet.first += T * m - (lst[it + 1] - lst[it]); profeet.second = min(profeet.second,profeet.first - T * m); it--; } } else{ cesh += profeet1.first; r = it1 - 1; one = false; profeet1 = {0,0}; while(it1 != N + 1 && (!one || profeet1.first < 0) ){ one = true; profeet1.first += T * m - (lst[it1] - lst[it1 - 1]); profeet1.second = min(profeet1.second,profeet1.first - T * m); it1++; } } } else if(cesh < -max(profeet.second, profeet1.second)){ break; } else{ if(cesh >= -profeet.second){ cesh += profeet.first; l = it + 1; one = false; profeet = {0,0}; while(it != 0 && (!one || profeet.first < 0) ){ one = true; profeet.first += T * m - (lst[it + 1] - lst[it]); profeet.second = min(profeet.second,profeet.first - T * m); it--; } } else{ cesh += profeet1.first; r = it1 - 1; one = false; profeet1 = {0,0}; while(it1 != N + 1 && (!one || profeet1.first < 0) ){ one = true; profeet1.first += T * m - (lst[it1] - lst[it1 - 1]); profeet1.second = min(profeet1.second,profeet1.first - T * m); it1++; } } } } if(cesh < 2 * lst[N]){ if(l == 1){ while(r != N){ if(cesh >= lst[r + 1] - lst[r]){ cesh += T * m - (lst[r + 1] - lst[r]); } else break; r++; } } if(r == N){ while(l != 1){ if(cesh >= lst[l] - lst[l - 1]){ cesh += T * m - (lst[l] - lst[l - 1]); } else break; l--; } } } m/= 2; //printf("%d %d %d %lld\n\n",l,r,m,cesh); if( cesh >= 2 * lst[N] || (l == 1 && r == N) ){ e = m; } else s = m + 1; } printf("%d\n",s); }

Compilation message (stderr)

sparklers.cpp: In function 'int main()':
sparklers.cpp:10:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
sparklers.cpp:11:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |         scanf(" %d",&K);
      |         ~~~~~^~~~~~~~~~
sparklers.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         scanf(" %lld",&T);
      |         ~~~~~^~~~~~~~~~~~
sparklers.cpp:14:42: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         for(int i = 1; i <= N; i++) scanf(" %d",&lst[i]);
      |                                     ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...