Submission #151703

#TimeUsernameProblemLanguageResultExecution timeMemory
151703Ruxandra985Bali Sculptures (APIO15_sculpture)C++14
0 / 100
2 ms420 KiB
/// aliens pe subtaskuri suna... mInUnAt #include <cstdio> #include <iostream> #define DIMN 2010 #define INF 4000000000000 using namespace std; int v[DIMN],cnt[DIMN],n; long long dp[DIMN],sp[DIMN]; int check (long long lambda , long long &sol){ /// sol = dp[n] , return = cnt[n] int i,poz,j; long long mini; for (i=1;i<=n;i++){ mini = (dp[i-1] | v[i]) + lambda * (cnt[i-1] + 1); poz = i-1; for (j=i-2;j>=0;j--){ if (mini > (dp[j] | (sp[i] - sp[j])) + lambda*(cnt[j] + 1)){ mini = (dp[j] | (sp[i] - sp[j])) + lambda*(cnt[j] + 1); poz = j; } } dp[i] = (dp[poz] | (sp[i] - sp[poz])); cnt[i] = cnt[poz] + 1; } sol = dp[n] + lambda * cnt[n]; return cnt[n]; } int main() { FILE *fin = stdin; FILE *fout = stdout; int a,b,i,x; long long sol , solfinal,st,dr,mid,lastok; fscanf (fin,"%d%d%d",&n,&a,&b); for (i=1;i<=n;i++){ fscanf (fin,"%d",&v[i]); sp[i] = sp[i-1] + v[i]; } if (a!=1){ solfinal =0; for (x=a;x<=b;x++){ /// aliens pe FIX x intervale st = -INF/2; dr = INF/2; while (st<=dr){ mid = (st + dr)/2; sol = 0; if (check(mid,sol) > x) st = mid + 1; else { lastok = mid; dr = mid - 1; } } sol = 0; check (lastok,sol); if (x == a) solfinal = sol - (long long)x * lastok; else solfinal = min (solfinal , sol - (long long)x * lastok); } } else { /// a = 1 , b e idk , deci poti sa selectezi CEL MULT b intervale solfinal = 0; st = -INF/2; dr = INF/2; while (st<=dr){ mid = (st + dr)/2; sol = 0; if (check(mid,sol) > b) st = mid + 1; else{ lastok = mid; dr = mid - 1; } } sol = 0; x = check (lastok,sol); solfinal = sol - (long long)x * lastok; } fprintf (fout,"%lld",solfinal); return 0; }

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:33:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d%d",&n,&a,&b);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:35:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d",&v[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~
sculpture.cpp:75:11: warning: 'lastok' may be used uninitialized in this function [-Wmaybe-uninitialized]
         x = check (lastok,sol);
         ~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...