QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#416365#7185. Poor Studentsgrass8cowRE 1ms5772kbC++172.1kb2024-05-21 19:42:322024-05-21 19:42:34

Judging History

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

  • [2024-05-21 19:42:34]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:5772kb
  • [2024-05-21 19:42:32]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,m,c[50100][20],a[20];
bool vis[50010];
#define pb push_back
#define ll long long
#define pi pair<int,int>
#define fi first
#define se second
vector<int>g[15];
multiset<pi>s[15][15];
bool ts[50100][20];
void ad(int u,int v,int z){
    if(z==1)assert(!ts[u][v]);
    if(z==-1)assert(ts[u][v]);
    ts[u][v]^=1;
    for(int i=1;i<=m;i++)if(v!=i){
        if(z)s[v][i].insert({-c[u][v]+c[u][i],u});
        else s[v][i].erase(s[v][i].find({-c[u][v]+c[u][i],u}));
    }
}
const ll I=1e18;
ll w[15][15],di[15];int pr[15],di2[15];
bool vi[15];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&c[i][j]),g[j].pb(i);
    for(int j=1;j<=m;j++){
        for(int i=1;i<=n;i++)g[j].pb(i);
        sort(g[j].begin(),g[j].end(),[&](int x,int y){return c[x][j]>c[y][j];});
    }
    for(int i=1;i<=m;i++)scanf("%d",&a[i]);
    ll ans=0;
    for(int st=1;st<=n;st++){
        for(int i=1;i<=m+2;i++)for(int j=1;j<=m+2;j++)
        w[i][j]=I;
        for(int i=1;i<=m;i++){
            while(vis[g[i].back()])g[i].pop_back();
            w[m+1][i]=c[g[i].back()][i];
            if(a[i]>0)w[i][m+2]=0;
        }
        for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)if(!s[i][j].empty())w[i][j]=(*s[i][j].begin()).fi;
        for(int i=1;i<=m+2;i++)di[i]=I;
        di[m+1]=di2[m+1]=0;queue<int>q;q.push(m+1),vi[m+1]=1;
        while(!q.empty()){
            int u=q.front();q.pop();vi[u]=0;
            for(int i=1;i<=m+2;i++)if(di[i]>di[u]+w[u][i]||di[i]==di[u]+w[u][i]&&di2[i]>di2[u]+1){
                di[i]=di[u]+w[u][i],pr[i]=u,di2[i]=di2[u]+1;
                if(!vi[i])q.push(i),vi[i]=1;
            }
        }
        ans+=di[m+2];
        int u=m+2;while(u!=m+1){
            int t=pr[u];
            if(u==m+2)a[t]--;
            else if(t==m+1){
                vis[g[u].back()]=1;
                ad(g[u].back(),u,1);
            }
            else{
                int z=(*s[t][u].begin()).se;
                ad(z,t,-1),ad(z,u,1);
            }
            u=t;
        }
    }
    return printf("%lld",ans),0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5772kb

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: 3992kb

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: -100
Runtime Error

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:


result: