Submission #3274499


Source Code Expand

#include <bits/stdc++.h> 

using namespace std;
using LL = long long int;

#define int long long

const int MAX_N = 4005;
const int MAX_T = 4005;

template<typename T>
class ConvexHullTrick {
private:
	// 直線群(配列)
	std::vector<std::pair<T, T>> lines;
	// 最小値(最大値)を求めるxが単調であるか
	bool isMonotonicX;
	// 最小/最大を判断する関数
	std::function<bool(T l, T r)> comp;

public:
	// コンストラクタ ( クエリが単調であった場合はflag = trueとする )
	ConvexHullTrick(bool flagX = true, std::function<bool(T l, T r)> compFunc = [](T l, T r) {return l >= r; })
		:isMonotonicX(flagX), comp(compFunc)  {
		// lines.emplace_back(-114514, -114514);
	};

	// 直線l1, l2, l3のうちl2が不必要であるかどうか
	bool check(std::pair<T, T> l1, std::pair<T, T> l2, std::pair<T, T> l3) {
		if (l1 < l3) std::swap(l1, l3);
		return (l3.second - l2.second) * (l2.first - l1.first) >= (l2.second - l1.second) * (l3.first - l2.first);
	}

	// 直線y=ax+bを追加する
	void add(T a, T b) {
		std::pair<T, T> line(a, b);
		while (lines.size() >= 2 && check(*(lines.end() - 2), lines.back(), line))
			lines.pop_back();
		lines.emplace_back(line);
	}

	// i番目の直線f_i(x)に対するxの時の値を返す
	T f(int i, T x) {
		return lines[i].first * x + lines[i].second;
	}

	// i番目の直線f_i(x)に対するxの時の値を返す
	T f(std::pair<T, T> line, T x) {
		return line.first * x + line.second;
	}

	// 直線群の中でxの時に最小(最大)となる値を返す
	T get(T x) {
		// 最小値(最大値)クエリにおけるxが単調
		if (isMonotonicX) {
			while (lines.size() - head >= 2 && comp(f(head, x), f(head + 1, x)))
				++head;
			return f(head, x);
		}
		else {
			int low = -1, high = lines.size() - 1;
			while (high - low > 1) {
				int mid = (high + low) / 2;
				(comp(f(mid, x), f(mid + 1, x)) ? low : high) = mid;
			}
			return f(high, x);
		}
	}

    bool isContains() {
        return lines.size() > 0;
    }

    int head = 0;
};


int N;
int T;

class Song{
public:
    int t, p, f;
    bool operator < (const Song& song) const {
        return f < song.f;
    }
}songList[MAX_N];

int dp[MAX_N][MAX_T];

signed main()
{
    cin >> N >> T;

    for(int i = 0; i < N; i++) {
        cin >> songList[i].t >> songList[i].p >> songList[i].f;
    }
    sort(songList, songList+N);

    vector<ConvexHullTrick<int> > cht;
    for(int i = 0; i <= T; i++) {
        cht.push_back(ConvexHullTrick<int>(true, less<int>()));
    }

    int ans = 0;
    for(int i = 1; i <= N; i++) {
        const Song& song = songList[i-1];
        for(int t = T; song.t <= t; t--) {
            if(t == song.t) {
                dp[i][t] = song.p;
            } else {
                if(!cht[t-song.t].isContains()) {
                    continue;
                }
                dp[i][t] = max(dp[i][t], song.p - song.f * song.f + cht[t-song.t].get(song.f));
            }
            cht[t].add(2*song.f, dp[i][t] - song.f*song.f);
            ans = max(ans, dp[i][t]);
            // cerr << i << " " << t << " " << dp[i][t] << endl;
        }
    }

    cout << ans << endl;

    return 0;
}

Submission Info

Submission Time
Task I - Live Programming
User takoshi
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3309 Byte
Status WA
Exec Time 602 ms
Memory 142172 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 18
WA × 61
Set Name Test Cases
All 00_sample_00, 00_sample_01, 00_sample_02, 00_sample_03, 00_sample_04, 01_rando_medium_031, 01_rando_medium_035, 01_rando_medium_160, 01_rando_medium_278, 01_rando_medium_337, 01_rando_medium_342, 01_rando_medium_355, 01_rando_medium_452, 01_rando_medium_467, 01_rando_medium_665, 02_rando_large_000, 02_rando_large_013, 02_rando_large_048, 02_rando_large_054, 02_rando_large_083, 02_rando_large_147, 02_rando_large_164, 02_rando_large_227, 02_rando_large_283, 02_rando_large_336, 02_rando_large_368, 05_attack_00, 05_attack_01, 05_attack_mi0803_00, 10_random_small_000, 10_random_small_001, 10_random_small_002, 10_random_small_003, 10_random_small_004, 10_random_small_005, 10_random_small_006, 10_random_small_007, 10_random_small_008, 10_random_small_009, 11_rando_medium_000, 11_rando_medium_001, 11_rando_medium_002, 11_rando_medium_003, 11_rando_medium_004, 11_rando_medium_005, 11_rando_medium_006, 11_rando_medium_007, 11_rando_medium_008, 11_rando_medium_009, 12_random_large_000, 12_random_large_001, 12_random_large_002, 12_random_large_003, 12_random_large_004, 12_random_large_005, 12_random_large_006, 12_random_large_007, 12_random_large_008, 12_random_large_009, 22_shortMusics_Large_000, 22_shortMusics_Large_001, 22_shortMusics_Large_002, 22_shortMusics_Large_003, 22_shortMusics_Large_004, 22_shortMusics_Large_005, 22_shortMusics_Large_006, 22_shortMusics_Large_007, 22_shortMusics_Large_008, 22_shortMusics_Large_009, 41_separate_medium_000, 41_separate_medium_001, 41_separate_medium_002, 41_separate_medium_003, 41_separate_medium_004, 42_separate_large_000, 42_separate_large_001, 42_separate_large_002, 42_separate_large_003, 42_separate_large_004
Case Name Status Exec Time Memory
00_sample_00 AC 1 ms 256 KB
00_sample_01 AC 1 ms 256 KB
00_sample_02 AC 1 ms 256 KB
00_sample_03 AC 1 ms 256 KB
00_sample_04 AC 1 ms 256 KB
01_rando_medium_031 WA 1 ms 384 KB
01_rando_medium_035 WA 1 ms 512 KB
01_rando_medium_160 WA 1 ms 512 KB
01_rando_medium_278 WA 2 ms 2560 KB
01_rando_medium_337 WA 1 ms 384 KB
01_rando_medium_342 WA 2 ms 2560 KB
01_rando_medium_355 WA 1 ms 384 KB
01_rando_medium_452 WA 2 ms 2560 KB
01_rando_medium_467 WA 2 ms 2560 KB
01_rando_medium_665 WA 1 ms 512 KB
02_rando_large_000 WA 18 ms 68224 KB
02_rando_large_013 WA 3 ms 6784 KB
02_rando_large_048 WA 6 ms 21120 KB
02_rando_large_054 WA 25 ms 88704 KB
02_rando_large_083 WA 16 ms 60160 KB
02_rando_large_147 WA 2 ms 2560 KB
02_rando_large_164 WA 24 ms 88704 KB
02_rando_large_227 WA 24 ms 90752 KB
02_rando_large_283 WA 33 ms 119936 KB
02_rando_large_336 WA 28 ms 107392 KB
02_rando_large_368 WA 19 ms 72448 KB
05_attack_00 WA 2 ms 2560 KB
05_attack_01 WA 1 ms 512 KB
05_attack_mi0803_00 WA 1 ms 384 KB
10_random_small_000 AC 1 ms 256 KB
10_random_small_001 AC 1 ms 256 KB
10_random_small_002 AC 1 ms 256 KB
10_random_small_003 AC 1 ms 256 KB
10_random_small_004 AC 1 ms 256 KB
10_random_small_005 AC 1 ms 256 KB
10_random_small_006 AC 1 ms 256 KB
10_random_small_007 AC 1 ms 256 KB
10_random_small_008 AC 1 ms 256 KB
10_random_small_009 AC 1 ms 256 KB
11_rando_medium_000 AC 1 ms 384 KB
11_rando_medium_001 WA 1 ms 512 KB
11_rando_medium_002 WA 1 ms 384 KB
11_rando_medium_003 WA 2 ms 2560 KB
11_rando_medium_004 WA 1 ms 512 KB
11_rando_medium_005 WA 1 ms 384 KB
11_rando_medium_006 WA 2 ms 2560 KB
11_rando_medium_007 AC 1 ms 256 KB
11_rando_medium_008 WA 2 ms 2560 KB
11_rando_medium_009 AC 1 ms 384 KB
12_random_large_000 WA 139 ms 80476 KB
12_random_large_001 WA 126 ms 60892 KB
12_random_large_002 WA 349 ms 131676 KB
12_random_large_003 WA 21 ms 12380 KB
12_random_large_004 WA 219 ms 131804 KB
12_random_large_005 WA 51 ms 31324 KB
12_random_large_006 WA 255 ms 108508 KB
12_random_large_007 WA 13 ms 8284 KB
12_random_large_008 WA 110 ms 50140 KB
12_random_large_009 WA 118 ms 79196 KB
22_shortMusics_Large_000 WA 329 ms 94812 KB
22_shortMusics_Large_001 WA 295 ms 110172 KB
22_shortMusics_Large_002 WA 547 ms 142172 KB
22_shortMusics_Large_003 WA 602 ms 140380 KB
22_shortMusics_Large_004 WA 418 ms 129244 KB
22_shortMusics_Large_005 WA 545 ms 133212 KB
22_shortMusics_Large_006 WA 368 ms 94556 KB
22_shortMusics_Large_007 WA 457 ms 110172 KB
22_shortMusics_Large_008 WA 239 ms 98160 KB
22_shortMusics_Large_009 WA 302 ms 92764 KB
41_separate_medium_000 WA 1 ms 512 KB
41_separate_medium_001 WA 2 ms 2560 KB
41_separate_medium_002 WA 1 ms 2560 KB
41_separate_medium_003 WA 1 ms 2560 KB
41_separate_medium_004 WA 2 ms 2560 KB
42_separate_large_000 WA 30 ms 93040 KB
42_separate_large_001 WA 30 ms 70620 KB
42_separate_large_002 WA 25 ms 68444 KB
42_separate_large_003 WA 42 ms 113628 KB
42_separate_large_004 WA 30 ms 74716 KB