QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#173072 | #7185. Poor Students | ucup-team139# | TL | 3392ms | 7068kb | C++23 | 3.4kb | 2023-09-09 21:51:13 | 2023-09-09 21:51:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define f first
#define s second
template<class T> using V = vector<T>;
using vi = V<int>;
using vpi = V<pair<int,int>>;
#define sz(x) int((x).size())
#define pb push_back
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define each(a,x) for (auto& a: x)
#define all(x) begin(x), end(x)
template<class T> bool ckmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; } // set $a = \min(a,b)$
struct MCMF { // 0-based, archi direzionati
using F = int; using C = ll; // flow type, cost type
struct Edge { int to, rev; F flo, cap; C cost; };
int N; V<C> p, dist; vpi pre; V<V<Edge>> adj;
void init(int _N) { N = _N;
p.resize(N),adj.resize(N),dist.resize(N),pre.resize(N);}
void ae(int u, int v, F cap, C cost) { assert(cap >= 0);
adj[u].pb({v,sz(adj[v]),0,cap,cost});
adj[v].pb({u,sz(adj[u])-1,0,0,-cost});
}
//send flow through lowest cost path
bool path(int s, int t) {
const C inf = numeric_limits<C>::max();
dist.assign(N,inf);
using T = pair<C,int>;
queue<T> todo;//(or queue<T>)
todo.push({dist[s] = 0,s});
while (sz(todo)) { // Dijkstra (or SPFA)
T x = todo.front(); todo.pop(); //(or todo.front())
if (x.f > dist[x.s]) x.f = dist[x.s]; //(or x.f = dist[x.s])
//all weights should be non-negative
each(e,adj[x.s]) {
if (e.flo < e.cap && ckmin(dist[e.to],
x.f+e.cost+p[x.s]-p[e.to])) {
pre[e.to]={x.s,e.rev};
todo.push({dist[e.to],e.to});
}
}
} // if costs are doubles, add some EPS so you
// don't traverse ~0-weight cycle repeatedly
return dist[t] != inf; // true if augmenting path
}
pair<F,C> calc(int s, int t) { assert(s != t);
F0R(_,5)F0R(i,N)each(e,adj[i])//utile con grafi densi...
if(e.cap)ckmin(p[e.to],p[i]+e.cost);//e archi negativi
F totFlow = 0; C totCost = 0;
while (path(s,t)) { // p -> potentials for Dijkstra
F0R(i,N)p[i]+=dist[i];//don't matter for unreachable
F df = numeric_limits<F>::max();
for (int x = t; x != s; x = pre[x].f) {
Edge& e = adj[pre[x].f][adj[x][pre[x].s].rev];
ckmin(df,e.cap-e.flo); }
totFlow += df; totCost += (p[t]-p[s])*df;
for (int x = t; x != s; x = pre[x].f) {
Edge& e = adj[x][pre[x].s]; e.flo -= df;
adj[pre[x].f][e.rev].flo += df;
}
} // get max flow you can send along path
return {totFlow,totCost};
}
};
void solve(int t){
int n,k;
cin>>n>>k;
MCMF ds;
int source = n+k, sink = n+k+1;
ds.init(n+k+2);
for(int i=0;i<n;i++){
ds.ae(source,i,1,0);
for(int j=0;j<k;j++){
int c;
cin>>c;
ds.ae(i,n+j,1,c);
}
}
for(int i=0;i<k;i++){
int a;
cin>>a;
ds.ae(n+i,sink,a,0);
}
cout<<ds.calc(source,sink).second<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)solve(i);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3500kb
input:
6 2 1 2 1 3 1 4 1 5 1 6 1 7 3 4
output:
12
result:
ok answer is '12'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
3 3 1 2 3 2 4 6 6 5 4 1 1 1
output:
8
result:
ok answer is '8'
Test #3:
score: 0
Accepted
time: 101ms
memory: 4196kb
input:
1000 10 734 303 991 681 755 155 300 483 702 442 237 256 299 675 671 757 112 853 759 233 979 340 288 377 718 199 935 666 576 842 537 363 592 349 494 961 864 727 84 813 340 78 600 492 118 421 478 925 552 617 517 589 716 7 928 638 258 297 706 787 266 746 913 978 436 859 701 951 137 44 815 336 471 720 2...
output:
92039
result:
ok answer is '92039'
Test #4:
score: 0
Accepted
time: 3392ms
memory: 7068kb
input:
5000 10 14 114 254 832 38 904 25 147 998 785 917 694 750 372 379 887 247 817 999 117 802 15 799 515 316 42 69 247 95 144 727 398 509 725 682 456 369 656 693 955 923 1 681 631 962 826 233 963 289 856 165 491 488 832 111 950 853 791 929 240 509 843 667 970 469 260 447 477 161 431 514 903 627 236 144 3...
output:
461878
result:
ok answer is '461878'
Test #5:
score: -100
Time Limit Exceeded
input:
10000 10 307 205 765 487 504 526 10 581 234 583 448 443 39 992 976 363 335 588 588 169 920 787 896 822 47 358 230 631 136 299 141 159 414 852 922 945 513 76 111 189 616 104 83 792 24 68 164 975 615 472 150 108 848 517 7 153 107 283 452 165 94 370 910 662 226 720 975 214 324 407 636 65 963 859 590 3 ...