Submission #8488924


Source Code Expand

Copy
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 309;

int a[N];
int b[N];
long long f[N][N];
long long nf[N][N];

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) {
    scanf("%d", a + i);
    b[i] = a[i];
  }
  b[n] = 0;
  sort(b, b + n + 1);
  const long long inf = 1'000'000'000'000'000'000;
  for (int i = 0; i <= m; ++i) {
    for (int j = 0; j <= n; ++j) {
      f[i][j] = inf;
    }
  }
  f[0][0] = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= m; ++j) {
      for (int k = 0; k <= n; ++k) {
        nf[j][k] = inf;
      }
    }
    for (int j = 0; j <= m; ++j) {
      {
        long long mn = inf;
        for (int k = 0; k <= n; ++k) {
          if (j + 1 <= m) { 
            mn = min(mn, f[j][k]);
            nf[j + 1][k] = min(nf[j + 1][k], mn);
            if (k + 1 <= n) {
              mn += b[k + 1] - b[k];
            }
          }
        }
      } 
      {
        long long mn = inf;
        for (int k = n; k >= 0; --k) {
          if (j + 1 <= m) { 
            mn = min(mn, f[j][k]);
            nf[j + 1][k] = min(nf[j + 1][k], mn);
          }
        }
      }
      int p = -1;
      for (int k = 0; k <= n; ++k) {
        if (b[k] == a[i]) {
          p = k;
        }
      }
      for (int k = 0; k <= n; ++k) {
        nf[j][p] = min(nf[j][p], f[j][k] + max(0, b[p] - b[k]));
      }
    }
    for (int j = 0; j <= m; ++j) {
      for (int k = 0; k <= n; ++k) {
        f[j][k] = nf[j][k];
      }
    }
  }
  long long ans = inf;
  for (int i = 0; i <= m; ++i) {
    for (int j = 0; j <= n; ++j) {
      ans = min(ans, f[i][j]);
    }
  }
  printf("%lld\n", ans);
}

Submission Info

Submission Time
Task F - Laminate
User fragusbot
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1756 Byte
Status AC
Exec Time 202 ms
Memory 1664 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:15:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &m);
                        ^
./Main.cpp:17:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", a + i);
                       ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 23
Set Name Test Cases
Sample Sample_01.txt, Sample_02.txt, Sample_03.txt
All Sample_01.txt, Sample_02.txt, Sample_03.txt, case_01.txt, case_02.txt, case_03.txt, case_04.txt, case_05.txt, case_06.txt, case_07.txt, case_08.txt, case_09.txt, case_10.txt, case_11.txt, case_12.txt, case_13.txt, case_14.txt, case_15.txt, case_16.txt, case_17.txt, case_18.txt, case_19.txt, case_20.txt
Case Name Status Exec Time Memory
Sample_01.txt AC 1 ms 128 KB
Sample_02.txt AC 1 ms 128 KB
Sample_03.txt AC 1 ms 128 KB
case_01.txt AC 113 ms 1024 KB
case_02.txt AC 118 ms 1152 KB
case_03.txt AC 127 ms 1024 KB
case_04.txt AC 132 ms 1152 KB
case_05.txt AC 136 ms 1152 KB
case_06.txt AC 146 ms 1152 KB
case_07.txt AC 150 ms 1280 KB
case_08.txt AC 155 ms 1280 KB
case_09.txt AC 165 ms 1408 KB
case_10.txt AC 169 ms 1408 KB
case_11.txt AC 1 ms 128 KB
case_12.txt AC 1 ms 128 KB
case_13.txt AC 202 ms 1664 KB
case_14.txt AC 202 ms 1664 KB
case_15.txt AC 101 ms 896 KB
case_16.txt AC 101 ms 896 KB
case_17.txt AC 102 ms 896 KB
case_18.txt AC 101 ms 896 KB
case_19.txt AC 101 ms 896 KB
case_20.txt AC 101 ms 896 KB