fork download
copy 
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC optimize("unroll-loops")
  3. #pragma GCC optimize("inline")
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. template<class T> struct cLtraits_identity{
  7.   using type = T;
  8. }
  9. ;
  10. template<class T> using cLtraits_try_make_signed =
  11.   typename conditional<
  12.     is_integral<T>::value,
  13.     make_signed<T>,
  14.     cLtraits_identity<T>
  15.     >::type;
  16. template <class S, class T> struct cLtraits_common_type{
  17.   using tS = typename cLtraits_try_make_signed<S>::type;
  18.   using tT = typename cLtraits_try_make_signed<T>::type;
  19.   using type = typename common_type<tS,tT>::type;
  20. }
  21. ;
  22. template<class S, class T> inline auto min_L(S a, T b)
  23. -> typename cLtraits_common_type<S,T>::type{
  24.   return (typename cLtraits_common_type<S,T>::type) a <= (typename cLtraits_common_type<S,T>::type) b ? a : b;
  25. }
  26. inline int my_getchar_unlocked(){
  27.   static char buf[1048576];
  28.   static int s = 1048576;
  29.   static int e = 1048576;
  30.   if(s == e && e == 1048576){
  31.     e = fread_unlocked(buf, 1, 1048576, stdin);
  32.     s = 0;
  33.   }
  34.   if(s == e){
  35.     return EOF;
  36.   }
  37.   return buf[s++];
  38. }
  39. inline void rd(int &x){
  40.   int k;
  41.   int m=0;
  42.   x=0;
  43.   for(;;){
  44.     k = my_getchar_unlocked();
  45.     if(k=='-'){
  46.       m=1;
  47.       break;
  48.     }
  49.     if('0'<=k&&k<='9'){
  50.       x=k-'0';
  51.       break;
  52.     }
  53.   }
  54.   for(;;){
  55.     k = my_getchar_unlocked();
  56.     if(k<'0'||k>'9'){
  57.       break;
  58.     }
  59.     x=x*10+k-'0';
  60.   }
  61.   if(m){
  62.     x=-x;
  63.   }
  64. }
  65. inline int rd_int(void){
  66.   int x;
  67.   rd(x);
  68.   return x;
  69. }
  70. struct MY_WRITER{
  71.   char buf[1048576];
  72.   int s;
  73.   int e;
  74.   MY_WRITER(){
  75.     s = 0;
  76.     e = 1048576;
  77.   }
  78.   ~MY_WRITER(){
  79.     if(s){
  80.       fwrite_unlocked(buf, 1, s, stdout);
  81.     }
  82.   }
  83. }
  84. ;
  85. MY_WRITER MY_WRITER_VAR;
  86. void my_putchar_unlocked(int a){
  87.   if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
  88.     fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
  89.     MY_WRITER_VAR.s = 0;
  90.   }
  91.   MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
  92. }
  93. template<class T> inline void wt_L(vector<T> x);
  94. template<class T> inline void wt_L(set<T> x);
  95. template<class T> inline void wt_L(multiset<T> x);
  96. template<class T1, class T2> inline void wt_L(pair<T1,T2> x);
  97. inline void wt_L(char a){
  98.   my_putchar_unlocked(a);
  99. }
  100. inline void wt_L(int x){
  101.   int s=0;
  102.   int m=0;
  103.   char f[10];
  104.   if(x<0){
  105.     m=1;
  106.     x=-x;
  107.   }
  108.   while(x){
  109.     f[s++]=x%10;
  110.     x/=10;
  111.   }
  112.   if(!s){
  113.     f[s++]=0;
  114.   }
  115.   if(m){
  116.     my_putchar_unlocked('-');
  117.   }
  118.   while(s--){
  119.     my_putchar_unlocked(f[s]+'0');
  120.   }
  121. }
  122. inline void wt_L(const char c[]){
  123.   int i=0;
  124.   for(i=0;c[i]!='\0';i++){
  125.     my_putchar_unlocked(c[i]);
  126.   }
  127. }
  128. int main(){
  129.   int TEST;
  130.   int N;
  131.   int W;
  132.   int X[101][101];
  133.   int val[101][101][101];
  134.   int dp[101][101];
  135.   int s;
  136.   int Nzj9Y0kE = rd_int();
  137.   for(TEST=(0);TEST<(Nzj9Y0kE);TEST++){
  138.     int i, k;
  139.     wt_L("Case #");
  140.     wt_L(TEST+1);
  141.     wt_L(": ");
  142.     rd(N);
  143.     rd(W);
  144.     {
  145.       int QAAnbtfa;
  146.       int om7Ebh6q;
  147.       for(QAAnbtfa=(0);QAAnbtfa<(N);QAAnbtfa++){
  148.         for(om7Ebh6q=(0);om7Ebh6q<(W);om7Ebh6q++){
  149.           rd(X[QAAnbtfa][om7Ebh6q]);
  150.         }
  151.       }
  152.     }
  153.     for(k=(0);k<(W);k++){
  154.       int i;
  155.       for(i=(0);i<(N);i++){
  156.         int j;
  157.         val[k][i][i] = X[i][k];
  158.         for(j=(i+1);j<(N);j++){
  159.           val[k][i][j] =min_L(val[k][i][j-1], X[j][k]);
  160.         }
  161.       }
  162.     }
  163.     for(i=(0);i<(N);i++){
  164.       int RlTT0MFE;
  165.       remove_reference<decltype(val[RlTT0MFE][i][i])>::type ClGtuHe4;
  166.       int BRSo37Cn = 0;
  167.       if((0) > ((W)-1)){
  168.         ClGtuHe4 = 0;
  169.       }
  170.       else{
  171.         for(RlTT0MFE = 0; RlTT0MFE <= (W)-1; RlTT0MFE++){
  172.           if(BRSo37Cn == 0){
  173.             ClGtuHe4 = val[RlTT0MFE][i][i];
  174.             BRSo37Cn = 1;
  175.             continue;
  176.           }
  177.           ClGtuHe4 += val[RlTT0MFE][i][i];
  178.         }
  179.         if(BRSo37Cn==0){
  180.           ClGtuHe4 = 0;
  181.         }
  182.       }
  183.       dp[i][i] =ClGtuHe4;
  184.     }
  185.     for(i=(N)-1;i>=(0);i--){
  186.       int j;
  187.       for(j=(i+1);j<(N);j++){
  188.         int U_95anlx;
  189.         remove_reference<decltype(val[U_95anlx][i][j])>::type EEPmwYOn;
  190.         int hUQRwZho = 0;
  191.         if((0) > ((W)-1)){
  192.           EEPmwYOn = 0;
  193.         }
  194.         else{
  195.           for(U_95anlx = 0; U_95anlx <= (W)-1; U_95anlx++){
  196.             if(hUQRwZho == 0){
  197.               EEPmwYOn = val[U_95anlx][i][j];
  198.               hUQRwZho = 1;
  199.               continue;
  200.             }
  201.             EEPmwYOn += val[U_95anlx][i][j];
  202.           }
  203.           if(hUQRwZho==0){
  204.             EEPmwYOn = 0;
  205.           }
  206.         }
  207.         s =EEPmwYOn;
  208.         int ROdgCjAq;
  209.         remove_reference<decltype(dp[i][ROdgCjAq]+dp[ROdgCjAq+1][j]-s)>::type EMcy9lTZ;
  210.         int Cn8Hwvol = 0;
  211.         if((i) > ((j)-1)){
  212.           EMcy9lTZ = numeric_limits<remove_reference<decltype(dp[i][ROdgCjAq]+dp[ROdgCjAq+1][j]-s)>::type>::max();
  213.         }
  214.         else{
  215.           for(ROdgCjAq = i; ROdgCjAq <= (j)-1; ROdgCjAq++){
  216.             if(Cn8Hwvol == 0){
  217.               EMcy9lTZ = dp[i][ROdgCjAq]+dp[ROdgCjAq+1][j]-s;
  218.               Cn8Hwvol = 1;
  219.               continue;
  220.             }
  221.             const auto w83Weq_n = dp[i][ROdgCjAq]+dp[ROdgCjAq+1][j]-s;
  222.             if(EMcy9lTZ > w83Weq_n){
  223.               EMcy9lTZ = w83Weq_n;
  224.             }
  225.           }
  226.           if(Cn8Hwvol==0){
  227.             EMcy9lTZ = numeric_limits<remove_reference<decltype(dp[i][ROdgCjAq]+dp[ROdgCjAq+1][j]-s)>::type>::max();
  228.           }
  229.         }
  230.         dp[i][j] =EMcy9lTZ;
  231.       }
  232.     }
  233.     wt_L(2*dp[0][N-1]);
  234.     wt_L('\n');
  235.   }
  236.   return 0;
  237. }
  238. template<class T> inline void wt_L(vector<T> x){
  239.   int fg = 0;
  240.   for(auto a : x){
  241.     if(fg){
  242.       my_putchar_unlocked(' ');
  243.     }
  244.     fg = 1;
  245.     wt_L(a);
  246.   }
  247. }
  248. template<class T> inline void wt_L(set<T> x){
  249.   int fg = 0;
  250.   for(auto a : x){
  251.     if(fg){
  252.       my_putchar_unlocked(' ');
  253.     }
  254.     fg = 1;
  255.     wt_L(a);
  256.   }
  257. }
  258. template<class T> inline void wt_L(multiset<T> x){
  259.   int fg = 0;
  260.   for(auto a : x){
  261.     if(fg){
  262.       my_putchar_unlocked(' ');
  263.     }
  264.     fg = 1;
  265.     wt_L(a);
  266.   }
  267. }
  268. template<class T1, class T2> inline void wt_L(pair<T1,T2> x){
  269.   wt_L(x.first);
  270.   my_putchar_unlocked(' ');
  271.   wt_L(x.second);
  272. }
  273. // cLay version 20220312-1
  274.  
  275. // --- original code ---
  276. // int N, W, X[101][101];
  277. // int val[101][101][101], dp[101][101], s;
  278. // REP(TEST,rd_int()){
  279. //   wtF("Case #{TEST+1}: ");
  280. //   rd(N,W,X(N,W));
  281. //   rep(k,W) rep(i,N){
  282. //     val[k][i][i] = X[i][k];
  283. //     rep(j,i+1,N) val[k][i][j] = min(val[k][i][j-1], X[j][k]);
  284. //   }
  285. //   rep(i,N) dp[i][i] = sum[k,0,W](val[k][i][i]);
  286. //   rrep(i,N) rep(j,i+1,N){
  287. //     s = sum[k,0,W](val[k][i][j]);
  288. //     dp[i][j] = min[k,i,j](dp[i][k]+dp[k+1][j]-s);
  289. //   }
  290. //   wt(2*dp[0][N-1]);
  291. // }
  292.  
Time limit exceeded #stdin #stdout 5s 5380KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/JWIl68
language:
C++ (gcc 8.3)
created:
3 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!