Submission #1211751

#TimeUsernameProblemLanguageResultExecution timeMemory
1211751ASGA_RedSeaDetecting Molecules (IOI16_molecules)C++17
9 / 100
0 ms328 KiB
/** * بسم الله الرحمن الرحيم * ﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿ */ /// author : "ASGA" #pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; using ll = long long; vector<int>find_subset(int l,int r,vector<int>a){ vector<ll>w(a.begin(),a.end()); if(accumulate(w.begin(),w.end(),0LL)<l)return {}; int n=a.size(); vector<vector<int>>f(r+1); for(int i=0;i<n;i++){ if(a[i]<=r){ f[a[i]].push_back(i); } } sort(a.rbegin(),a.rend()); vector<int>d(r+1,-1); d[0]=0; int mx=0; for(int&i:a){ for(int j=r;j>=i;j--){ if(d[j-i]!=-1){ d[j]=j-i; mx=max(mx,j); } } if(mx>=l)break; } if(mx<l)return {}; vector<int>ret; ll tot=0; int mmx=mx; while(mx>0){ assert(d[mx]!=-1&&d[d[mx]]!=-1); ret.push_back(f[mx-d[mx]].back()); f[mx-d[mx]].pop_back(); mx=d[mx]; } for(int&i:ret)tot+=w[i]; //assert(tot==mmx); return ret; }

Compilation message (stderr)

molecules.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
molecules_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...