| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 749542 |
2023-05-28T07:35:30 Z |
박상훈(#9965) |
Popeala (CEOI16_popeala) |
C++17 |
|
96 ms |
2840 KB |
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
constexpr int INF = 1e18;
int dp[55][20020], opt[55][20020], a[20020], aS[20020], bS[55][20020], n, t, s;
char b[55][20020];
ll bt[20020];
list<array<ll, 3>> dq[55];
int f(int l, int r){
int ret = 0;
for (int i=1;i<=n;i++){
if (bS[i][r] - bS[i][l-1] == r-l+1) ret += aS[r] - aS[l-1];
}
return ret;
}
signed main(){
scanf("%lld %lld %lld", &n, &t, &s);
for (int i=1;i<=t;i++){
scanf("%lld", a+i);
aS[i] = aS[i-1] + a[i];
}
for (int i=1;i<=n;i++){
scanf("%s", b[i]+1);
for (int j=1;j<=t;j++){
bS[i][j] = bS[i][j-1] + (b[i][j]=='1');
}
}
for (int i=1;i<=t;i++){
for (int j=1;j<=n;j++) if (b[j][i]=='1') bt[i] |= 1LL<<j;
}
for (int i=1;i<=n;i++) bt[0] |= 1LL<<i;
fill(dp[0]+1, dp[0]+t+1, INF);
dp[0][0] = 0;
for (int z=1;z<=s;z++){
for (int c=0;c<=n;c++) dq[c].clear();
for (int i=0;i<=t;i++){
dp[z][i] = INF;
for (int c=1;c<=n;c++) if (!dq[c].empty()){
while(!dq[c].empty() && (dq[c].front()[2] & bt[i]) != dq[c].front()[2]){
auto p = dq[c].front(); dq[c].pop_front();
p[2] &= bt[i];
int idx = __builtin_popcountll(p[2]);
p[1] += idx * p[0] - c * p[0];
while(!dq[idx].empty() && dq[idx].back()[1] >= p[1]) dq[idx].pop_back();
dq[idx].push_back(p);
}
}
for (int c=0;c<=n;c++) if (!dq[c].empty()) dp[z][i] = min(dp[z][i], dq[c].front()[1] + aS[i] * c);
// printf("\ni = %lld\n", i);
// for (int i=0;i<=n;i++){
// for (auto &[x, y, z]:dq[i]) printf("(%lld, %lld, %lld) ", x, y, z);
// printf("\n");
// }
// printf("-> %lld\n", dp[z][i]);
int idx = __builtin_popcountll(bt[0]);
array<ll, 3> p = {-aS[i], dp[z-1][i] - aS[i] * idx, bt[0]};
while(!dq[idx].empty() && dq[idx].back()[1] >= p[1]) dq[idx].pop_back();
dq[idx].push_back(p);
}
printf("%lld\n", dp[z][t]);
// dp[z][0] = INF;
// for (int i=1;i<=t;i++){
// dp[z][i] = INF;
// for (int j=0;j<i;j++){
// ll val = (ll)dp[z-1][j] + f(j+1, i);
// if (dp[z][i] > val){
// dp[z][i] = val;
// opt[z][i] = j;
// }
// }
// }
// cout << dp[z][t] << '\n';
// for (int i=1;i<=t;i++) printf("%lld ", dp[z][i]);
// printf("\n");
// for (int i=1;i<=t;i++) printf("%lld ", opt[z][i]);
// printf("\n");
// for (int i=1;i<t;i++) assert(opt[z][i] <= opt[z][i+1]);
}
}
Compilation message
popeala.cpp: In function 'int main()':
popeala.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
21 | scanf("%lld %lld %lld", &n, &t, &s);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
23 | scanf("%lld", a+i);
| ~~~~~^~~~~~~~~~~~~
popeala.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
27 | scanf("%s", b[i]+1);
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
692 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
1356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
2840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
692 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
