Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.

Id	Date	User	Problem	Result	Time	Mem	Lang
1072	20/05/2013 12:38:56	agarwaen	C - City	Accepted	140	3.7 KiB	GNU G++ 5.1.0

Code

#include <iostream>
#include <algorithm>
using namespace std;

#define FOR(i,n) for (int i = 1; i <= (n); ++i)
#define REP(i,n) for (int i = 0; i < (n); ++i)

#define DB(x) cout << #x << " = " << x << endl;

const int MAX = 100010;

struct store
{
	int x, y, c, yidx;
} s[MAX];

int N, M, K;
int idx[MAX];
int t[MAX];

bool cmpY(int a, int b)
{
	if (s[a].y != s[b].y)
		return s[a].y < s[b].y;
	return s[a].x < s[b].x;
}

bool cmpX(int a, int b)
{
	if (s[a].x != s[b].x)
		return s[a].x < s[b].x;
	return s[a].y < s[b].y;
}

void update(int x, int v)
{
	for (int i = x; i <= K; i += (i & -i)) t[i] = max(t[i], v);
}

int query(int x)
{
	int r = 0;
	for (int i = x; i; i -= (i & -i)) r = max(r, t[i]);
	return r;
}

int main()
{
	ios::sync_with_stdio(false);

cin >> N >> M >> K;
	FOR(i, K) cin >> s[i].x >> s[i].y >> s[i].c;

FOR(i, K) idx[i] = i;

sort(idx+1, idx+K+1, cmpY);

FOR(i, K) s[ idx[i] ].yidx = i;

sort(idx+1, idx+K+1, cmpX);

FOR(i, K)
	{
		int y = s[ idx[i] ].yidx;
		int c = s[ idx[i] ].c;
		int v = query(y);
		update(y, v+c);
	}

cout << query(K) << endl;

return 0;
}// UH++

Judgement Details

Test 1: 0.027 0.000 1424K ok
Test 2: 0.010 0.000 1424K ok
Test 3: 0.062 0.031 2612K ok
Test 4: 0.070 0.062 2612K ok
Test 5: 0.110 0.078 3768K ok
Test 6: 0.146 0.094 3776K ok
Test 7: 0.155 0.125 3768K ok
Test 8: 0.169 0.125 3776K ok
Test 9: 0.189 0.140 3776K ok
Accepted

Matcom Online Grader Faculty of Mathematics and Computer Science of University of Havana

Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana