Submission #1124942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124942		sleepntsheep	스트랩 (JOI14_straps)	C11	100 / 100	5 ms	440 KiB

straps

#include <stdio.h>
#include <limits.h>

#define N 2000
int n, a[N], b[N], o, p, ii[N], jj[N], rity;
long long dp[N + 1], ans, ans2, ans3, run;

int main()
{
  int i, j, k;
  scanf("%d", &n);
  rity = 1;
  for (i = 0; i < n; ++i)
  {
    scanf("%d%d", a + i, b + i);
    if (b[i] >= 0)
    {
      if (a[i])
      {
        ans += b[i];
        rity += a[i] - 1;
      }
      else
        jj[p++] = i;
    }
  }

  for (i = 1; i < n; ++i)
    dp[i] = -1e18;
  dp[0] = 0;

  for (i = 0; i < n; ++i)
  {
    if (b[i] < 0)
    {
      --a[i];
      if (a[i] <= 0)
        continue;
      if (a[i] > p)
        a[i] = p;
      for (j = p; j >= a[i]; --j)
      {
        if (dp[j] < dp[j - a[i]] + b[i])
          dp[j] = dp[j - a[i]] + b[i];
      }
      for (j = p - 1; j >= 0; --j)
        if (dp[j] < dp[j + 1])
          dp[j] = dp[j + 1];

    }
  }

  for (j = 0; j < p; ++j)
    for (i = 1; i < p; ++i)
    {
      if (b[jj[i - 1]] < b[jj[i]])
      {
        k = jj[i];
        jj[i] = jj[i - 1];
        jj[i - 1] = k;
      }
    }

  for (i = 0; i < rity && i < p; ++i)
    ans += b[jj[i]];

  for (i = rity; i < p; ++i)
  {
    run += b[jj[i]];
    ans3 = dp[i - rity + 1] + run;
    if (ans3 > ans2)
      ans2 = ans3;
  }

  printf("%lld", ans + ans2);
  return 0;
}

Compilation message (stderr)

straps.c: In function 'main':
straps.c:11:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |   scanf("%d", &n);
      |   ^~~~~~~~~~~~~~~
straps.c:15:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf("%d%d", a + i, b + i);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 45 / 45
• Subtask 4: 45 / 45