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;
  9.     long long int K[maxn+1],H[maxn+1],S[maxn+1],tmp,ans=-maxc-1,c,c2,cost,opt;
  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.  
  16.     for(h=-1;h<=1;h+=2){// Két eset van: vagy az első sziget irányába utazunk (h=-1)
  17.                         // vagy az utolsó, n-edik sziget irányába (h=1), ez utóbbi eset
  18.                         // megkapható, ha a szigeteket és költségeket megfordítjuk
  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.     c=0;pos=1;
  25.     cost=0;
  26.     for(i=1;i<=n;i++){
  27.         // c a minimális haszon, ha a k<=i-edik szigetről indulunk és az elsőn állunk meg
  28.         // , a k-dik szigetre való utazási költséget nem számítva
  29.         // és az ottani kincset sem!
  30.         if(i>1){
  31.            c2=cost-S[i-1];// itt cost az (i-1)-ről az első szigetre való utazás haszna
  32.            if(c2<c){c=c2;pos=i;}
  33.         }
  34.  
  35.         cost+=K[i];
  36.         if(i>1)cost-=S[i-1];
  37.         // cost a haszon, ha az i-edik szigetről indulunk, és az elsőn állunk meg,
  38.         // az i-edikre való utazási költséget nem számolva
  39.  
  40.         opt=cost-c-H[i];// a max. haszon, ha az i-edik szigetről indulunk az első sziget "irányába",
  41.                         // pos-dik szigeten állunk meg
  42.         if(opt>ans){ans=opt;if(h==-1){st=i;en=pos;inc=-1;}
  43.                             else{st=n+1-i;en=n+1-pos;inc=1;}// szigetek visszafordítása         
  44.         }
  45.     }}
  46.  
  47.     printf("%lld\n",ans);
  48.     len=st-en;if(len<0)len=-len;
  49.     printf("%d",len+1);// len az utazás hossza
  50.     for(i=st;;i+=inc){
  51.         printf(" %d",i);
  52.         if(i==en)break;
  53.     }
  54.     printf("\n");
  55.     return 0;
  56. }
  57.  
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/G1gOwR
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!