fork download
copy 
  1. #include <stdio.h>
  2.  
  3. #define maxn 200000
  4. #define maxc 1000000000
  5.  
  6. int main(void){
  7.  
  8.     int h,i,n,inc,pos,st,en,len,p1,p2,p3,p4,D0,D1,D2,x,inv;
  9.     long long int K[maxn+2],H[maxn+2],S[maxn+2],tmp,ans=-maxc-1,c1,c2,opt,v1,v2;
  10.  
  11.     scanf("%d",&n);
  12.     for(i=1;i<=n;i++)scanf("%lld",&K[i]);
  13.     for(i=1;i<=n;i++)scanf("%lld",&H[i]);
  14.     for(i=1;i<=n-1;i++)scanf("%lld",&S[i]);
  15.     S[n]=0;
  16.     H[n+1]=0;
  17.  
  18.     for(h=-1;h<=1;h+=2){
  19.     	if(h==1){// szigetek és költségek "megfordítása"
  20.             for(i=1;2*i<=n;i++){tmp=K[i];K[i]=K[n+1-i];K[n+1-i]=tmp;
  21.                                 tmp=H[i];H[i]=H[n+1-i];H[n+1-i]=tmp;}
  22.             for(i=1;2*i<=n-1;i++){tmp=S[i];S[i]=S[n-i];S[n-i]=tmp;}}        
  23.  
  24.     c1=0;p1=n;p2=n;
  25.     for(i=n;i>=1;i--){
  26.         // i<=e<=s: e-dik szigetre megyünk először, majd i-be, végül s-be
  27.         // 4 eset van: 
  28.         // e=i vagy nem (ekkor e>=i+1)
  29.         // s=i vagy nem (ekkor s>=i+1), de az s=i esetben e=i egy opt. választás
  30.  
  31.         // c2 lesz a max haszon ezen utak esetén, míg
  32.         // c1 lesz a max haszon az e=i spec. esetben
  33.  
  34.         // ha az i-dik szigetről indulunk, azaz e=i
  35.         // itt 2 eset van: s=i vagy s>i
  36.         v1=-H[i]+K[i];
  37.         v2=-H[i]+H[i+1]+K[i]-S[i]+c1;
  38.         if(v1>v2){c1=v1;p1=i;p2=i;}
  39.         else     {c1=v2;p1=i;}
  40.         if(c1>ans){ans=c1;D0=p1;D1=i;D2=p2;inv=(h==1);}
  41.  
  42.         if(i<n){
  43.         // e>i eset, ekkor s>i is feltehető, így
  44.         c2=K[i]-2*S[i]+c2;
  45.         if(c1>c2){c2=c1;p3=p1;p4=p2;}// a max haszon egy spec esetben valósult meg: e=i
  46.         if(c2>ans){ans=c2;D0=p3;D1=i;D2=p4;inv=(h==1);}}
  47.         else{p3=n;p4=n;c2=c1;}
  48.     }}
  49.  
  50.     printf("%lld\n",ans);
  51.     len=D0-D1+D2-D1+1;
  52.     printf("%d",len);// len az utazás hossza
  53.     // ha inv=1, akkor x->n+1-x a helyes sziget
  54.     for(i=D0;;i--){
  55.         x=i;if(inv)x=n+1-x;
  56.         printf(" %d",x);
  57.         if(i==D1)break;
  58.     }
  59.     for(i=D1+1;i<=D2;i++){
  60.         x=i;if(inv)x=n+1-x;
  61.         printf(" %d",x);
  62.     }
  63.     printf("\n");
  64.     return 0;
  65. }
  66.  
Success #stdin #stdout 0s 14888KB
comments (?)
stdin
copy 
5
0 10 15 12 1
1 100 200 50 5
50 3 1 15
stdout
copy 
14
4 5 4 3 2
https://ideone.com/hKIaTU
language:
C (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!