oj.uz

Submission #146683

# Submission time Handle Problem Language Result Execution time Memory
146683 2019-08-25T07:37:45 Z gs14004 Cake 3 (JOI19_cake3) C++17
0 / 100
 3 ms 760 KB 
#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)
        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 sc = 0; sc < n; sc++)
    {
        multiset<i64> largest;
        i64 sum = cakes[sc].xx;
 
        for (int bc = sc + 2; bc < n; bc++)
        {
            if (largest.size() < m - 2)
            {
                largest.insert(cakes[bc - 1].xx);
                sum += cakes[bc - 1].xx;
            }
            else if (*largest.begin() < cakes[bc - 1].xx)
            {
                sum += cakes[bc - 1].xx;
                sum -= *largest.begin();
                largest.erase(largest.begin());
                largest.insert(cakes[bc - 1].xx);
            }
 
            i64 total = sum + cakes[bc].xx - 2 * (cakes[bc].yy - cakes[sc].yy);
 
            if (largest.size() == m - 2)
                c[sc][bc] = total;
        }
    }
 
    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

cake3.cpp: In function 'int main()':
cake3.cpp:85:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (largest.size() < m - 2)
                 ~~~~~~~~~~~~~~~^~~~~~~
cake3.cpp:100:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (largest.size() == m - 2)
                 ~~~~~~~~~~~~~~~^~~~~~~~
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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Incorrect 3 ms 760 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Incorrect 3 ms 760 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 76.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Incorrect 3 ms 760 KB Output isn't correct
4 Halted 0 ms 0 KB -