Submission #199938

#	Time	Username	Problem	Language	Result	Execution time	Memory
199938		SamAnd	Potatoes and fertilizers (LMIO19_bulves)	C++17	24 / 100	548 ms	262148 KiB

bulves

#include <bits/stdc++.h>
using namespace std;
const int N = 500005, M = 30004;
const long long INF = 1000000009000000009;

int n;
int a[N], b[N];
long long sa, sb;

void solv1()
{
    long long ans = 0;
    int j = 1;
    for (int i = 1; i <= n; ++i)
    {
        while (1)
        {
            if (b[j] >= a[i])
            {
                ans += abs(i - j) * 1LL * a[i];
                b[j] -= a[i];
                a[i] = 0;
                break;
            }
            else
            {
                ans += abs(i - j) * 1LL * b[j];
                a[i] -= b[j];
                b[j] = 0;
                ++j;
            }
        }
    }
    printf("%lld\n", ans);
}

long long dp[M], ndp[M];
void solv3()
{
    vector<int> aa, bb;
    for (int i = 1; i <= n; ++i)
    {
        int minu = (a[i] - b[i]);
        a[i] -= minu;
        b[i] -= minu;
        for (int j = 0; j < a[i]; ++j)
            bb.push_back(i);
        for (int j = 0; j < b[i]; ++j)
            aa.push_back(i);
    }
    for (int j = 1; j <= bb.size(); ++j)
        dp[j] = INF;
    for (int i = 0; i < aa.size(); ++i)
    {
        memset(ndp, INF, sizeof ndp);
        for (int j = 0; j < bb.size(); ++j)
        {
            dp[j + 1] = min(dp[j + 1], dp[j]);
            ndp[j + 1] = min(ndp[j + 1], dp[j] + abs(aa[i] - bb[j]));
        }
        memcpy(dp, ndp, sizeof ndp);
    }
    long long ans = INF;
    for (int j = 0; j <= bb.size(); ++j)
        ans = min(ans, dp[j]);
    printf("%lld\n", ans);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d%d", &a[i], &b[i]);
        sa += a[i];
        sb += b[i];
    }
    if (sa == sb)
        solv1();
    else
        solv3();
    return 0;
}

Compilation message (stderr)

bulves.cpp: In function 'void solv3()':
bulves.cpp:51:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 1; j <= bb.size(); ++j)
                     ~~^~~~~~~~~~~~
bulves.cpp:53:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < aa.size(); ++i)
                     ~~^~~~~~~~~~~
bulves.cpp:55:36: warning: overflow in implicit constant conversion [-Woverflow]
         memset(ndp, INF, sizeof ndp);
                                    ^
bulves.cpp:56:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < bb.size(); ++j)
                         ~~^~~~~~~~~~~
bulves.cpp:64:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j <= bb.size(); ++j)
                     ~~^~~~~~~~~~~~
bulves.cpp: In function 'int main()':
bulves.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
bulves.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a[i], &b[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 24 / 24
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 36