QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#735801 | #9422. Two-star Contest | Ufowoqqqo | TL | 0ms | 0kb | C++14 | 1.7kb | 2024-11-11 21:44:49 | 2024-11-11 21:44:50 |
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m;
ll k;
cin>>n>>m>>k;
vector<int>s(n);
vector<vector<int>>p(n,vector<int>(m));
for(int i=0;i<n;i++)
{
cin>>s[i];
for(int j=0;j<m;j++)
cin>>p[i][j];
}
vector<int>id(n);
for(int i=0;i<n;i++)
id[i]=i;
sort(id.begin(),id.end(),[&](int x,int y){
return s[x]>s[y];
});
bool ok=true;
ll mx=1e18;
for(int i=0;i<n;)
{
int j=i;
while(j<n-1&&s[id[j+1]]==s[id[i]])
j++;
ll new_mx=mx;
for(;i<=j;i++)
{
int x=id[i];
ll sum=0,cnt=0;
for(int l=0;l<m;l++)
if(p[x][l]!=-1)sum+=p[x][l];
else cnt++;
if(sum>=mx)
{
ok=false;
break;
}
ll tar=min(mx-sum-1,cnt*k);
new_mx=min(new_mx,sum+tar);
for(int l=0;l<m;l++)
{
if(p[x][l]!=-1)continue;
ll cur=min(tar,k);
p[x][l]=cur;
tar-=cur;
}
}
mx=new_mx;
}
if(!ok)
{
cout<<"No"<<endl;
continue;
}
cout<<"Yes"<<endl;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
cout<<p[i][j]<<" ";
cout<<endl;
}
}
return 0;
}
详细
Test #1:
score: 0
Time Limit Exceeded
input:
5 3 4 5 5 1 3 -1 -1 2 -1 5 -1 5 3 3 -1 -1 4 2 3 10 10000 5 0 -1 1 10 10 10 2 3 10 10 1 2 3 100 4 5 6 2 3 10 100 1 2 3 10 4 5 6 2 3 10000 100 -1 -1 -1 1 -1 -1 -1
output:
Yes 1 3 5 5 2 5 0 5 3 5 1 4