제출 #678523

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
678523		vjudge1	Art Exhibition (JOI18_art)	C++17	100 / 100	176 ms	12188 KiB

art

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define vll vector<ll>
#define vllp vector<pair<ll, ll> >
#define vi vector <int>
#define vip vector <pair <int, int> >
#define db double
#define ldb long double
#define pdb pair <double, double> 
#define YES cout<<"Yes"
#define NO cout<<"No"
#define nl cout<<"\n"
#define vv vector <vector <int> >
#define pll pair <ll, ll> 
#define pi pair <int, int>
#define pb push_back
#define f first
#define s second
using namespace std;

const ll mod=1e9+7;
const ll modx=998244353;
const double eps=1e-9;
const ll INF=INT_MAX;
const ll INFINF=LLONG_MAX;
const int N=5e5;
int n;
vip v;
int dp[N+5];

void input()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		int x, y;
		cin >> x >> y;
		v.pb({x, y});
	}
	sort(v.begin(), v.end());
}

void solve()
{
	dp[1]=v[0].s;
	for(int i = 2; i <= n; i++)
	{
		dp[i]=v[i-1].s;
		dp[i]=max(dp[i], dp[i-1]+v[i-1].s-(v[i-1].f-v[i-2].f));
	}
	int ans=-INFINF;
	for(int i = 1; i <= n; i++)
	{
		ans=max(ans, dp[i]);
	}
	cout << ans;
}

signed main() 
{
//	auto start_time = chrono::high_resolution_clock::now();
//	freopen("DNA.inp", "r", stdin);
//	freopen("DNA.out", "w", stdout);
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int t=1;
// 	cin >> t;
	for(int i = 1; i <= t; i++)
	{
		input();
	    solve();
	    nl;
//	    cout << flush;
	}
//    auto end_time = chrono::high_resolution_clock::now();
//        double duration = chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count();
//        cout << "\n[ " << duration << " ms ]\n"; 
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50