oj.uz

Submission #125005

# Submission time Handle Problem Language Result Execution time Memory
125005 2019-07-04T10:37:51 Z eriksuenderhauf Popeala (CEOI16_popeala) C++11
100 / 100
 302 ms 6136 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<ll,int,hash<ll>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 55;
const int MAXT = 2e4 + 5;
const double eps = 1e-9;
int a[MAXT], dp[2][MAXT];
int bitsm[MAXT][MAXN], mi[MAXN];
char str[MAXT];

int main() {
	int n, t, s;
	scanf("%d %d %d", &n, &t, &s);
	for (int i = 1; i <= t; i++) {
		ni(a[i]);
		a[i] += a[i-1];
	}
	for (int i = 0; i < n; i++) {
		scanf("%s", str);
		for (int j = 1; j <= t; j++) {
			if (str[j-1] == '1')
				bitsm[j][i] = bitsm[j-1][i];
			else
				bitsm[j][i] = j;
		}
	}
	for (int i = 1; i <= t; i++) {
		bitsm[i][n] = i;
		sort(bitsm[i], bitsm[i]+n+1);
	}
	mem(dp, 0x3f);
	dp[0][0] = 0;
	for (int i = 1; i <= s; i++) {
		mem(mi, 0x3f);
		mem(dp[i&1], 0x3f);
		for (int j = 1; j <= t; j++) {
			for (int k = 0; k <= n; k++) {
				for (int l = bitsm[j-1][k]; l < bitsm[j][k]; l++)
					mi[k] = min(mi[k], dp[(i&1)^1][l] - a[l] * k);
				dp[i&1][j] = min(dp[i&1][j], mi[k] + a[j] * k);
			}
		}
		printf("%d\n", dp[i&1][t]);
	}
    return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &t, &s);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:9:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define ni(n) scanf("%d", &(n))
               ~~~~~^~~~~~~~~~~~
popeala.cpp:46:3: note: in expansion of macro 'ni'
   ni(a[i]);
   ^~
popeala.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", str);
   ~~~~~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 892 KB Output is correct
2 Correct 10 ms 760 KB Output is correct
3 Correct 11 ms 636 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1016 KB Output is correct
2 Correct 60 ms 1272 KB Output is correct
3 Correct 65 ms 1656 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 11 ms 892 KB Output is correct
4 Correct 10 ms 760 KB Output is correct
5 Correct 11 ms 636 KB Output is correct
6 Correct 44 ms 1016 KB Output is correct
7 Correct 60 ms 1272 KB Output is correct
8 Correct 65 ms 1656 KB Output is correct
9 Correct 81 ms 2324 KB Output is correct
10 Correct 143 ms 2868 KB Output is correct
11 Correct 216 ms 5956 KB Output is correct
12 Correct 226 ms 6024 KB Output is correct
13 Correct 301 ms 5988 KB Output is correct
14 Correct 299 ms 6008 KB Output is correct
15 Correct 302 ms 6136 KB Output is correct