QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#820495 | #4438. Magic | SGColin | AC ✓ | 227ms | 2072kb | C++20 | 1.8kb | 2024-12-18 21:37:12 | 2024-12-18 21:37:16 |
Judging History
answer
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=10001,maxq=100,maxe=maxn+maxn+maxq;
int te,n,K,Q,a[maxn+5],sum;
int E,lnk[maxn+5],nxt[maxe+5],to[maxe+5],w[maxe+5];
LL dis[maxn+5];int que[maxn+5],cnt[maxn+5];bool vis[maxn+5];
#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
static char buf[100000],*l=buf,*r=buf;
return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
T tot=0;char ch=readc(),lst='+';
while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
inline void Add(int x,int y,int z) {to[++E]=y;w[E]=z;nxt[E]=lnk[x];lnk[x]=E;}
#define AMOD(x) ((x)+1<maxn?(x)+1:0)
LL Spfa(int S,int T){
for (int i=0;i<=n;i++) dis[i]=1e18,cnt[i]=0,vis[i]=false;
int Head=0,Tail=0;
dis[S]=0;que[++Tail]=S;vis[S]=true;
while (Head!=Tail){
int x=que[Head=AMOD(Head)];vis[x]=false;
if ((++cnt[x])>n) return -1;
for (int j=lnk[x],u;j;j=nxt[j])
if (dis[x]+w[j]<dis[u=to[j]]){
dis[u]=dis[x]+w[j];
if (!vis[u]) que[Tail=AMOD(Tail)]=u,vis[u]=true;
}
}
return -dis[T];
}
int main(){
for (readi(te);te;te--){
readi(n);readi(K);sum=0;
for (int i=1;i<=n;i++) readi(a[i]),sum+=a[i];
E=0;for (int i=0;i<=n;i++) lnk[i]=0;
for (int i=1;i<=n;i++) Add(i,i-1,0);
for (int i=1;i<=n;i++){
int L=max(i-K+1,1),R=min(i+K-1,n);
Add(R,L-1,-a[i]);
}
for (readi(Q);Q;Q--){
int L,R,B;readi(L);readi(R);readi(B);
Add(L-1,R,B);
}
// int L=0,R=sum;
// for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)){
// int temlnk=lnk[0];
// Add(0,n,mid);
// Spfa(n,0)<1e18?R=mid-1:L=mid+1;
// lnk[0]=temlnk;E--;
// }
printf("%lld\n",Spfa(n,0));
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 227ms
memory: 2072kb
input:
15 5 2 1 2 2 2 1 1 2 4 1 5 2 2 2 0 10 3 1 1 5 11 5 2 2 2 0 10 3 1 2 3 0 3 2 3 7 3 1 2 2 0 3 2 3 0 6 2 1 1 0 3 3 0 4393 1769 280 628 847 751 431 684 746 842 975 487 294 339 803 123 492 662 340 590 844 431 635 831 459 470 287 133 668 865 722 829 653 734 417 452 959 343 900 355 214 627 791 811 891 537 ...
output:
-1 -1 12 7 6 1995 2227 -1 1997 10580 6929 2000 1999 2000 3810
result:
ok 15 lines