QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#244483#7762. 数据库zhoukangyang#60 935ms20080kbC++112.4kb2023-11-09 09:56:592024-07-04 02:23:32

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 02:23:32]
  • 评测
  • 测评结果:60
  • 用时:935ms
  • 内存:20080kb
  • [2023-11-09 09:56:59]
  • 提交

answer

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define uint unsigned int
#define ull unsigned long long 
#define i128 __int128
using namespace std;
template < int N, int Ne >  struct flow { 
	using F = ll; // flow type
	F inf = 1e18;
	int n, s, t; // Remember to assign n, s and t !
	int ehd[N], pre[N], cur[N], ev[Ne << 1], enx[Ne << 1], eid = 1;
	void clear() {
		eid = 1, memset(ehd, 0, sizeof(ehd));
	}
	F ew[Ne << 1], ec[Ne << 1], dis[N];
	void Eadd(int u, int v, F w, F c) {
		++eid, enx[eid] = ehd[u], ew[eid] = w, ec[eid] = c, ev[eid] = v, ehd[u] = eid;
	}
	void add(int u, int v, F w, F c) {
		Eadd(u, v, w, c), Eadd(v, u, 0, -c);
	}
	bool spfa() {
		queue < int > q;
		L(i, 1, n) dis[i] = inf, cur[i] = ehd[i]; 
		q.push(s), dis[s] = 0;
		while(!q.empty()) {
			int u = q.front();
			q.pop();
			for(int i = ehd[u]; i; i = enx[i]) if(ew[i] && dis[ev[i]] > dis[u] + ec[i]) {
				dis[ev[i]] = dis[u] + ec[i], pre[ev[i]] = i, q.push(ev[i]);
			}
		}
//		L(i, 1, n + 3) cout << dis[i] << " "; 
//		cout << "\n";
		return dis[t] < inf;
	}
	pair < F, F > max_flow() {
		F res1 = 0, res2 = 0;
		while(spfa()) {
			F o = inf;
			for(int x = t; x != s; x = ev[pre[x] ^ 1]) o = min(o, ew[pre[x]]);
			for(int x = t; x != s; x = ev[pre[x] ^ 1]) ew[pre[x]] -= o, ew[pre[x] ^ 1] += o;
			res1 += o, res2 += o * dis[t];
//			cout << dis[t] << " : " << o << "\n";
		}
		return make_pair(res1, res2);
	}
} ; 

const int N = 2e5 + 7;

flow < N, N * 2 > G;

int n, m, q;
int idl[N], idr[N];
int w[N], K[N], lst[N];
int main () {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> q;
	G.s = ++G.n, G.t = ++G.n;
	L(i, 1, n) {
		cin >> w[i];
	}
	L(i, 0, q + 1) {
		idl[i] = ++G.n;
		idr[i] = ++G.n;
	}
	L(i, 1, q) {
		G.add(G.s, idl[i], 1, 0);
		G.add(idr[i], G.t, 1, 0);
	}
	G.add(G.s, idl[0], m, 0);
	G.add(idr[q + 1], G.t, m, 0);
	L(i, 1, q) {
		cin >> K[i];
		if(lst[K[i]]) {
			G.add(idl[lst[K[i]]], idr[i], 1, 0);
		}
		lst[K[i]] = i;
	}
	
	int pre = idl[0];
	L(i, 1, q) {
		G.add(pre, idr[i], 1, w[K[i]]);
		++G.n;
		G.add(pre, G.n, m, 0);
		G.add(idl[i], G.n, m, 0);
		pre = G.n;
	}
	G.add(pre, idr[q + 1], m, 0);
	auto mp = G.max_flow();
	cout << mp.second << '\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 935ms
memory: 20080kb

input:

10 3 5000
23077 34848 88221 8067 83132 62621 41320 69146 32971 27594
2 7 5 3 9 6 1 9 4 8 1 8 8 3 6 9 1 7 5 5 6 8 1 3 10 6 8 7 10 2 1 2 6 7 5 5 9 5 7 10 10 6 6 7 2 4 3 1 10 10 5 1 1 6 1 2 8 9 2 5 10 1 10 7 5 5 10 5 2 5 6 10 9 5 6 3 5 3 6 5 7 4 1 5 8 1 1 9 7 1 1 2 1 8 6 2 9 8 4 2 5 4 5 2 10 4 3 6 9 7 ...

output:

100598924

result:

ok single line: '100598924'

Test #2:

score: 0
Accepted
time: 873ms
memory: 18252kb

input:

10 4 5000
54224 55364 32836 46635 99179 26033 49587 15072 63093 94302
4 7 8 4 1 2 6 3 1 1 6 10 5 7 2 9 3 9 1 5 7 3 8 4 7 2 5 3 5 4 1 6 4 10 4 10 8 1 5 7 9 7 9 1 6 1 10 10 10 5 1 1 3 5 10 1 8 8 6 8 8 10 6 9 7 6 1 1 5 3 10 8 6 5 8 7 5 8 4 8 8 1 8 6 4 5 8 10 7 6 7 2 10 7 10 10 3 1 3 5 5 7 3 2 5 3 1 7 6...

output:

85562058

result:

ok single line: '85562058'

Test #3:

score: 0
Accepted
time: 887ms
memory: 19984kb

input:

10 5 5000
8091 5917 35634 83114 46741 61842 48134 41606 63881 20560
8 7 9 5 1 4 10 9 10 9 8 5 5 7 5 1 5 9 4 1 4 7 9 4 10 4 4 2 9 1 5 1 2 6 10 1 5 4 5 3 3 1 6 7 5 7 10 2 5 8 2 9 3 5 3 1 2 4 5 10 4 4 10 4 8 2 8 6 4 1 3 6 8 2 6 2 2 5 9 4 2 8 3 10 8 7 2 1 10 6 5 8 2 8 9 3 9 5 6 6 7 2 7 3 10 9 10 2 4 7 2...

output:

43892491

result:

ok single line: '43892491'

Subtask #2:

score: 0
Time Limit Exceeded

Test #4:

score: 0
Time Limit Exceeded

input:

10 2 5000
65644 5214 85000 40719 98071 56616 35404 16019 96748 89032
5 9 6 1 3 6 8 10 2 9 1 10 5 9 9 9 2 7 7 7 7 10 5 1 3 10 4 2 5 5 2 8 3 2 1 3 3 6 2 4 5 5 2 5 2 3 4 2 10 1 4 6 10 9 6 4 9 10 5 3 9 7 7 2 1 9 5 8 8 4 8 8 4 5 6 1 3 4 8 10 4 3 6 6 9 2 5 2 8 5 10 4 7 10 3 9 3 2 9 3 10 7 1 3 9 9 3 5 1 3 ...

output:

173524192

result:


Subtask #3:

score: 20
Accepted

Test #7:

score: 20
Accepted
time: 7ms
memory: 15884kb

input:

5000 15 400
34145 93322 29976 7963 53362 50640 10859 94528 13329 49980 18826 50286 60155 79748 73253 18329 5216 83079 48220 98825 46592 76855 14037 19859 80960 4461 377 70496 28092 99806 5355 27013 92051 95231 65553 32365 3862 89764 86063 93033 12754 68996 38965 52942 69948 34370 3023 52079 16066 57...

output:

19341503

result:

ok single line: '19341503'

Test #8:

score: 0
Accepted
time: 8ms
memory: 17976kb

input:

5000 15 400
68511 70579 96844 20943 72871 28340 68790 60294 76760 12623 80406 65418 37942 2849 76307 28818 18555 42151 94506 78241 15350 11345 76323 21860 22703 31009 24763 71007 60858 53746 28720 5027 72512 39122 55299 41675 88475 94331 78711 3464 80345 69031 98746 14792 97862 97255 5853 92742 9096...

output:

19515326

result:

ok single line: '19515326'

Test #9:

score: 0
Accepted
time: 8ms
memory: 17976kb

input:

5000 15 400
18305 15347 86331 37503 78391 3378 82447 51150 49032 2422 47659 20516 18666 16520 27948 17865 45842 66799 35584 75288 46358 21654 30233 25291 44810 27579 93986 15174 56012 48286 66826 93615 77979 40669 17262 77857 82134 50752 19642 77961 55856 68600 60598 33035 94214 17392 16736 21460 58...

output:

18253485

result:

ok single line: '18253485'

Subtask #4:

score: 20
Accepted

Test #10:

score: 20
Accepted
time: 30ms
memory: 17920kb

input:

10 5 1000
86764 81108 88408 93029 87155 18790 28170 29349 81866 77109
8 7 10 7 2 7 1 8 4 10 9 10 4 1 7 1 9 9 1 6 6 1 9 6 7 1 8 10 1 7 9 1 1 9 7 10 8 5 5 1 2 3 10 6 2 6 2 6 1 2 7 8 5 6 10 2 9 8 2 6 8 5 10 8 1 10 4 6 5 6 3 8 1 3 5 2 2 7 2 4 5 5 8 2 4 1 3 6 8 2 2 3 1 8 1 5 8 6 9 7 7 3 7 9 8 9 9 7 5 3 6...

output:

15248002

result:

ok single line: '15248002'

Test #11:

score: 0
Accepted
time: 21ms
memory: 17924kb

input:

10 10 1000
57793 91210 18011 676 38391 78527 56352 69343 95947 5616
5 8 4 5 10 6 1 7 3 10 2 7 1 9 5 3 5 8 3 8 7 10 2 10 6 1 4 3 6 10 6 3 8 4 3 9 1 6 10 3 10 1 6 2 9 9 3 5 8 8 3 9 1 5 9 9 3 3 7 9 2 4 1 9 8 3 1 2 8 9 10 9 4 3 10 5 4 4 8 6 6 9 3 3 2 3 7 2 3 3 10 4 5 5 6 4 2 5 10 1 2 6 9 8 7 9 4 8 2 1 2...

output:

511866

result:

ok single line: '511866'

Test #12:

score: 0
Accepted
time: 25ms
memory: 17904kb

input:

10 15 1000
19536 14188 62086 25660 67447 48774 97871 17167 8671 85361
3 5 2 6 4 6 10 5 7 6 10 8 1 9 5 7 5 5 2 10 7 10 8 6 3 4 2 2 8 9 6 10 9 10 10 9 6 1 7 2 1 10 8 10 3 9 1 8 10 4 6 9 9 8 1 5 2 10 9 1 3 6 5 6 2 5 3 9 6 5 6 10 5 6 10 4 6 6 8 8 9 5 2 10 1 10 7 4 2 6 10 5 6 2 3 1 3 9 8 3 9 7 7 7 2 6 7 ...

output:

446761

result:

ok single line: '446761'

Test #13:

score: 0
Accepted
time: 82ms
memory: 18136kb

input:

100 5 1000
95646 33117 46458 52069 38647 38645 60235 93897 41039 35835 49580 92470 5371 6812 38049 9178 50163 92322 9735 27037 58888 49095 68473 5472 1644 94513 50597 10246 96329 51334 1986 79907 89526 10771 29923 55249 59048 91934 46853 79352 85644 57708 57300 20536 70782 61882 58712 97314 45686 55...

output:

36018137

result:

ok single line: '36018137'

Test #14:

score: 0
Accepted
time: 79ms
memory: 17912kb

input:

100 10 1000
36326 35981 96633 82565 65884 23199 50344 49682 96971 42033 2351 31928 50056 73426 36217 89994 30603 27971 17757 19901 99501 35915 27895 26451 91714 36134 94294 19114 22490 97680 48272 80639 24603 93000 28420 7595 7314 52546 12258 58666 88422 29237 69223 41046 13515 72493 26486 34554 239...

output:

30951978

result:

ok single line: '30951978'

Test #15:

score: 0
Accepted
time: 74ms
memory: 18204kb

input:

100 15 1000
60259 28844 6884 35222 45974 11055 13021 13966 14853 85552 12283 29760 50104 63448 84364 1684 99886 31837 61724 84415 28292 81814 31562 60077 93784 1729 1602 56374 19276 89781 13359 78765 97380 34118 39756 12254 61197 53500 95962 61254 16553 24467 58101 53482 65199 75076 67326 92045 306 ...

output:

26014456

result:

ok single line: '26014456'

Test #16:

score: 0
Accepted
time: 106ms
memory: 18024kb

input:

1000 5 1000
84587 68464 19119 74315 48972 23581 58263 43666 21662 5458 47594 18617 52236 24283 45998 66734 8501 94413 31981 77247 50069 95649 21536 8055 62698 98164 14074 22987 14525 12396 7681 17830 97091 88885 86419 1067 92977 54999 33673 9550 67710 98546 82017 17583 667 36168 61540 74015 42193 48...

output:

45688268

result:

ok single line: '45688268'

Test #17:

score: 0
Accepted
time: 112ms
memory: 17908kb

input:

1000 10 1000
24129 67704 68122 93372 94874 19813 14041 20830 97805 57074 99877 64455 80825 93755 98668 89675 35445 42895 74964 71326 43884 8123 1767 83698 2892 77832 21668 85066 17440 49874 77903 22427 45669 41174 40029 27379 61235 13563 4313 90065 99573 45555 19683 39486 76606 30438 34528 180 83016...

output:

44994110

result:

ok single line: '44994110'

Test #18:

score: 0
Accepted
time: 111ms
memory: 18140kb

input:

1000 15 1000
59991 63683 65484 87716 79869 15955 13746 80474 77381 51499 17028 13036 18275 82716 12845 66038 16310 66787 28778 73107 90796 63216 85094 24799 99979 96956 35994 21067 81494 75695 91088 34745 82075 27522 293 67267 51879 50823 80429 54323 21127 60258 40463 26950 69326 7049 39530 62048 23...

output:

39885004

result:

ok single line: '39885004'

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%