Submission #677965

#TimeUsernameProblemLanguageResultExecution timeMemory
677965arnold518Remittance (JOI19_remittance)C++17
100 / 100
208 ms23816 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 1e6; int N; ll A[MAXN+10], B[MAXN+10], X[MAXN+10], S; bool solve(ll X) { ll t=X; for(int i=N; i>=1; i--) { X=X*2+B[i]-A[i]; if(X<0) return true; if(X>-S) return false; } return X<=t; } int main() { scanf("%d", &N); for(int i=1; i<=N; i++) scanf("%lld%lld", &A[i], &B[i]), S+=B[i]-A[i]; if(S>0) return !printf("No\n"); ll lo=0, hi=-S+1; while(lo+1<hi) { ll mid=lo+hi>>1; if(solve(mid)) lo=mid; else hi=mid; } ll t=lo, x=lo; for(int i=N; i>=1; i--) { x=x*2+B[i]-A[i]; if(x<0) return !printf("No\n"); if(x>-S) return !printf("No\n"); X[i]=x; } if(x!=t) return !printf("No\n"); for(int i=1; i<=N; i++) if(X[i]==0) return !printf("Yes\n"); bool flag=false; for(int i=1; i<=N; i++) if(B[i]!=0) flag=true; if(!flag) return !printf("No\n"); return !printf("Yes\n"); }

Compilation message (stderr)

remittance.cpp: In function 'int main()':
remittance.cpp:34:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |   ll mid=lo+hi>>1;
      |          ~~^~~
remittance.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
remittance.cpp:28:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |  for(int i=1; i<=N; i++) scanf("%lld%lld", &A[i], &B[i]), S+=B[i]-A[i];
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...