Submission #771307

#TimeUsernameProblemLanguageResultExecution timeMemory
771307HoriaHaivasSan (COCI17_san)C++14
48 / 120
126 ms65536 KiB
/* "TLE is like the wind, always by my side" - Yasuo - 2022 - */ #include <bits/stdc++.h> #define debug(x) cerr << #x << " " << x << "\n" #define debugs(x) cerr << #x << " " << x << " " #pragma GCC optimize("Ofast") #define int long long using namespace std; struct cladire { int h; int g; int poz; }; struct subsir { int sum; int highest; }; cladire building[42]; vector<subsir> firsthalf; int mars[42][(1<<19)+1];/// mars[i][j] = numarul de numere cu highest mai mic sau egal cu i in primele j numere din firsthalf int n,k,i,j,val,ans,r,pas,ree; bool cmp (cladire a, cladire b) { return a.h<b.h; } bool cmp2(subsir a, subsir b) { return a.sum<b.sum; } bool cmp3(cladire a, cladire b) { return a.poz<b.poz; } void gen(int r) { int mask,currsum,currhighest,j; bool ok; for (mask=0; mask<(1<<r); mask++) { ok=true; currsum=0; currhighest=-1; for (j=0; j<r && ok; j++) { if (mask&(1<<j)) { if (building[j+1].h>=currhighest) { currsum+=building[j+1].g; currhighest=building[j+1].h; } else { ok=false; } } } if (ok && currsum!=0) { if (currsum>=k) ans++; firsthalf.push_back({currsum,currhighest}); } } } void gen2(int r) { int mask,j,currsum,currhighest,currlowest; bool ok; for (mask=0; mask<(1<<r); mask++) { ok=true; currsum=0; currhighest=0; currlowest=n+1; for (j=0; j<r && ok; j++) { if (mask&(1<<j)) { if (building[j+n/2+1].h>=currhighest) { currsum+=building[j+n/2+1].g; currhighest=building[j+n/2+1].h; currlowest=min(currlowest,building[j+n/2+1].h); } else { ok=false; } } } if (ok && currsum!=0) { ree=0; pas=(1<<20); while (pas) { if (ree+pas<firsthalf.size() && currsum+firsthalf[ree+pas].sum<k) ree+=pas; pas=pas/2; } if (currsum+firsthalf[ree].sum<k) ree++; /* debugs(mask); debugs(currsum); debugs(currlowest); debugs(firsthalf[r].sum); debugs(r); debug(mars[currlowest][firsthalf.size()]-mars[currlowest][min(r-1,1LL*0)]); Doamne ajuta sa mearga (trebuia cu D mare) */ if (ree!=0) ans+=mars[currlowest][firsthalf.size()-1]-mars[currlowest][ree-1]; else ans+=mars[currlowest][firsthalf.size()-1]; if (currsum>=k) ans++; } } } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> k; for (i=1; i<=n; i++) { cin >> building[i].h >> building[i].g; building[i].poz=i; } sort(building+1,building+1+n,cmp); val=0; for (i=1; i<=n; i++) { if (i==1 || building[i].h!=building[i-1].h) val++; building[i].h=val; } sort(building+1,building+1+n,cmp3); ans=0; gen(n/2); sort(firsthalf.begin(),firsthalf.end(),cmp2); for (i=0; i<firsthalf.size(); i++) { mars[firsthalf[i].highest][i]++; for (j=1; j<=n; j++) { mars[j][i]+=mars[j-1][i]; } for (j=1;j<=n;j++) { mars[j][i]+=mars[j][i-1]; } } gen2(n/2); cout << ans; }

Compilation message (stderr)

san.cpp: In function 'void gen2(long long int)':
san.cpp:111:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<subsir>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |                 if (ree+pas<firsthalf.size() && currsum+firsthalf[ree+pas].sum<k)
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~
san.cpp: In function 'int main()':
san.cpp:159:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<subsir>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |     for (i=0; i<firsthalf.size(); i++)
      |               ~^~~~~~~~~~~~~~~~~
#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...