Submission #146679

#	Time	Username	Problem	Language	Result	Execution time	Memory
146679		jwvg0425	Cake 3 (JOI19_cake3)	C++17	0 / 100	3 ms	764 KiB

cake3

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

i64 c[2005][2005];
i64 big[2005];

void f(int y1, int y2, int x1, int x2)
{
    if (y1 > y2 || x1 > x2)
        return;

    i64 ans = -1ll << 60;
    i64 ansp = x1;

    int y = (y1 + y2) / 2;

    for (int i = x1; i <= x2; i++)
    {
        if (c[y][i] > ans)
        {
            ans = c[y][i];
            ansp = i;
        }
    }

    big[y] = ans;

    f(y1, y - 1, x1, ansp);
    f(y + 1, y2, ansp, x2);
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);

    vector<ii64> cakes(n);

    for (int i = 0; i < n; i++)
        scanf("%lld %lld", &cakes[i].xx, &cakes[i].yy);

    for (int i = 0; i < n; i++)
        big[i] = -1ll << 60;

    sort(all(cakes), [](const ii64& l, const ii64& r)
    {
        return l.yy < r.yy;
    });

    // c(i,j) 전처리
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            c[i][j] = -1ll << 60;
    
    for (int i = 0; i < n; i++)
    {
        multiset<i64> largest;
        i64 sum = 0;

        for (int j = i; j < n; j++)
        {
            if (largest.size() < m)
            {
                largest.insert(cakes[j].xx);
                sum += cakes[j].xx;
            }
            else if (*largest.begin() < cakes[j].xx)
            {
                sum -= *largest.begin();
                sum += cakes[j].xx;
                largest.erase(largest.begin());
                largest.insert(cakes[j].xx);
            }

            if (largest.size() == m)
                c[i][j] = sum - 2 * (cakes[j].yy - cakes[i].yy);
        }
    }

    f(0, n - 1, 0, n - 1);

    i64 ans = big[0];

    for (int i = 1; i < n; i++)
        ans = max(ans, big[i]);

    printf("%lld\n", ans);

    return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:85:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (largest.size() < m)
                 ~~~~~~~~~~~~~~~^~~
cake3.cpp:98:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (largest.size() == m)
                 ~~~~~~~~~~~~~~~^~~~
cake3.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
cake3.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld", &cakes[i].xx, &cakes[i].yy);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 19
• Subtask 3: 0 / 76