Submission #1095857

#TimeUsernameProblemLanguageResultExecution timeMemory
1095857RequiemBali Sculptures (APIO15_sculpture)C++17
46 / 100
4 ms3932 KiB
#include<bits/stdc++.h> #define int long long #define pb push_back #define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); #define MOD 1000000007 #define inf 1e18 #define fi first #define se second #define FOR(i,a,b) for(int i=a;i<=b;i++) #define FORD(i,a,b) for(int i=a;i>=b;i--) #define sz(a) ((int)(a).size()) #define endl '\n' #define pi 3.14159265359 #define TASKNAME "sculpture" using namespace std; template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; } template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; } typedef pair<int,int> ii; typedef pair<int,ii> iii; typedef vector<int> vi; const int MAXN = 2e3 + 9; int n, s1, s2; int a[MAXN], pre[MAXN]; namespace subtask1{ bool check(){ return n <= 20; } int res = inf; void backtrack(int pos,int curOR, int curPart){ // cout << pos << ' ' << curOR << ' ' << curPart << endl; if (curPart > s2) return; if (pos == n){ if (curPart >= s1) minimize(res, curOR); return; } FOR(nxt, pos + 1, n){ backtrack(nxt, curOR | (pre[nxt] - pre[pos]), curPart + 1); } } void solve(){ backtrack(0, 0, 0); cout << res << endl; } } namespace subtask2{ bool check(){ FOR(i, 1, n){ if (a[i] > 10) return false; } return n <= 50; } bool dp[53][23][513]; void solve(){ memset(dp, false, sizeof(dp)); dp[0][0][0] = true; FOR(i, 0, n){ FOR(parts, 0, min(i, s2)){ FOR(stateOR, 0, 511){ if (dp[i][parts][stateOR]){ // cout << i << ' ' << parts << ' ' << stateOR << endl; FOR(nxt, i + 1, n){ int s = pre[nxt] - pre[i]; dp[nxt][parts + 1][stateOR | s] = 1; } } } } } FOR(state, 0, 511){ FOR(i, s1, s2){ if (dp[n][i][state]) { cout << state << endl; return; } } } } } namespace subtask3{ bool check(){ FOR(i, 1, n){ if (a[i] > 20) return true; } return (s1 == 1 and n <= 100); } int dp[102][2059]; void solve(){ memset(dp, 0x3f, sizeof(dp)); dp[0][0] = 0; FOR(i, 0, n - 1){ FOR(stateOR, 0, 2047){ if (dp[i][stateOR] < 1e9){ FOR(nxt, i + 1, n){ minimize(dp[nxt][stateOR | (pre[nxt] - pre[i])], dp[i][stateOR] + 1); } } } } FOR(state, 0, 2047){ if (dp[n][state] <= s2) { cout << state << endl; return; } } } } namespace subtask4{ bool check(){ return n <= 100; } bool dp[102][102]; bool can(int msk){ memset(dp, false, sizeof(dp)); dp[0][0] = true; FOR(i, 1, n){ FOR(j, 1, min(i, s2)){ FOR(k, 0, i - 1){ int s = pre[i] - pre[k]; if ((s & msk) == s) dp[i][j] |= dp[k][j - 1]; } // if (msk == 11 and dp[i][j]) cout << i << ' ' << j << endl; } } FOR(i, s1, s2){ if (dp[n][i]) return true; } return false; } void solve(){ int cur = (1LL << 43) - 1; FORD(i, 42, 0){ if (can(cur ^ (1LL << i))){ cur ^= (1LL << i); } // cout << cur << endl; } cout << cur << endl; } } namespace subtask5{ bool check(){ return s1 == 1; } int dp[2002]; bool can(int msk){ memset(dp, 0x3f, sizeof(dp)); dp[0] = 0; FOR(i, 1, n){ FORD(j, i - 1, 0){ int s = pre[i] - pre[j]; if ((s & msk) == s) minimize(dp[i] , dp[j] + 1); } } return dp[n] <= s2; } void solve(){ int cur = (1LL << 43) - 1; FORD(i, 42, 0){ if (can(cur ^ (1LL << i))){ cur ^= (1LL << i); } } cout << cur << endl; } } main() { fast; if (fopen(TASKNAME".inp","r")){ freopen(TASKNAME".inp","r",stdin); freopen(TASKNAME".out","w",stdout); } cin >> n >> s1 >> s2; FOR(i, 1, n){ cin >> a[i]; pre[i] = pre[i - 1] + a[i]; } if (subtask1::check()) return subtask1::solve(), 0; if (subtask2::check()) return subtask2::solve(), 0; if (subtask3::check()) return subtask3::solve(), 0; if (subtask4::check()) return subtask4::solve(), 0; if (subtask5::check()) return subtask5::solve(), 0; } /** Warning: Cận lmao Code imple thiếu case nào không. Limit. **/

Compilation message (stderr)

sculpture.cpp:185:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  185 | main()
      | ^~~~
sculpture.cpp: In function 'int main()':
sculpture.cpp:189:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  189 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:190:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  190 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...