2023 ICPC 网络赛Ⅱ DIM 现场 code | JorbanS

D

#include 
#define Cases int __; cin >> __; for (int _ = 1; _ <= __; _ ++)

using namespace std;
typedef long long ll;
const int N = 502;
int g[N][N];
bool row[N], col[N];
int rowN, colN;

ll solve() {
	int n; cin >> n;
	ll res = 0;
	rowN = colN = 0;
	for (int i = 1; i <= n; i ++) row[i] = col[i] = false;
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= n; j ++) {
			cin >> g[i][j];
			if (g[i][j] <= 0) {
			    if (!row[i]) rowN ++;
			    if (!col[j]) colN ++;
			    row[i] = col[j] = true;
			    res += g[i][j];
			}
		}
	}
	ll ROW = res, COL = res;
	for (int i = 1; i <= n; i ++) {
		if (row[i]) continue;
		int t = 1e6;
		for (int j = 1; j <= n; j ++) t = min(t, g[i][j]);
		ROW += t;
	}
	for (int i = 1; i <= n; i ++) {
		if (col[i]) continue;
		int t = 1e6;
		for (int j = 1; j <= n; j ++) t = min(t, g[j][i]);
		COL += t;
	}
	return min(ROW, COL);
}

int main() {
	Cases
	cout << solve() << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

I

#include 
#define Cases int __; cin >> __; for (int _ = 1; _ <= __; _ ++)

using namespace std;
const int N = 5e5 + 2;
int a[N];

double solve() {
	int n; cin >> n;
	for (int i = 0; i < n; i ++) cin >> a[i];
	double res = n;
	for (int i = 0; i < n; i ++) {
		double q; cin >> q;
		if (q) {
			q *= 1e-5;
			int A = i - a[i];
			res = min(res, i + (A - A * q + 1) / q);
		}
	}
	return res;
}

int main() {
	Cases
	{
		printf("%.12lf", solve());
		if (_ != __) cout << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

M

#include 
#include 
#define Cases int __; cin >> __; for (int _ = 1; _ <= __; _ ++)

using namespace std;
const int N = 5e3 + 2;
int a[N], b[N];
double p[N], t[N], pre[N];

double solve() {
	int n; cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i] >> b[i] >> p[i];
		t[i] = a[i] + b[i] * p[i];
	}
	sort(t + 1, t + n + 1);
	double res = 0;
	for (int i = 1; i <= n; i ++) res = res * 2 + t[i];
	return res;
}

int main() {
	Cases
	{
		printf("%.12lf", solve());
		if (_ != __) cout << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28