akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define rp(i,n) for(int i=0; i<n; i++)
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
#define INF 100000000000000ll

int main(){
    ll n,m,l;
    cin >> n >> m >> l;
    vector<vector<P>> G(n+1,vector<P>(0));
    rp(i,m){
        ll a,b,c;
        cin >> a >> b >> c;
        G[a].push_back(make_pair(c,b));
        G[b].push_back(make_pair(c,a));
    }
    ll memo[n+1][n+1];
    for(ll i=1; i<=n; i++){
        priority_queue<P,vector<P>,greater<P>> que;
        vector<ll> minpath(n+1,INF);
        minpath[i]=0;
        que.push(make_pair(0,i));
        while(!que.empty()){
            P p=que.top(); que.pop();
            //cout << p.first << " " << p.second << endl;
            ll v=p.second;
            if(minpath[v]<p.first) continue;

            for(auto nextp : G[v]){
                if(nextp.first>l) continue;
                if((minpath[v]+nextp.first)%10000000000ll>l){
                    if(minpath[nextp.second]>(minpath[v]/10000000000ll+1)*10000000000ll+nextp.first){
                        minpath[nextp.second]=(minpath[v]/10000000000ll+1)*10000000000ll+nextp.first;
                        que.push(make_pair(minpath[nextp.second],nextp.second));
                        //cout << "Yeah" << endl;
                    }
                }
                else{
                    if(minpath[nextp.second]>minpath[v]+nextp.first){
                        minpath[nextp.second]=minpath[v]+nextp.first;
                        que.push(make_pair(minpath[nextp.second],nextp.second));
                        //cout << "YeahYeah" << endl;
                    }
                }
            }

        }
        for(int j=1; j<=n; j++){
            memo[i][j]=minpath[j];
        }
    }
    int q;
    cin >> q;
    vector<ll> ans(q);
    rp(i,q){
        ll s,t;
        cin >> s >> t;
        if(memo[s][t]<10000000000000ll) ans[i]=memo[s][t]/10000000000ll;
        else ans[i]=-1;
    }
    rp(i,q) cout << ans[i] << endl;
    return 0;
    
}

Measured memory_bytes: 4428
#include<stdio.h>

int main(){
 int x = 0, max = 0, l, N;
 char S[101];
 scanf("%d", &N);
 scanf("%s", S);
 for(l = 0; l < N; l++){
  if(S[l] == 'I') x++;
  else if(S[l] == 'D') x--;
  if(x > max) max = x;
 }
printf("%d\n", max);
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ll long long int
#define pii pair<int,int>
#define mod 1000000007
#define eps 0.000000001
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define ln(x) ((int)x.length())
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define dbg(x) cout<<#x<<": "<<x<<endl;
const double PI = acos(-1.0);
using namespace std;

void cp()
{
    int n, k;
    cin >> k >> n;
    vector<int> arr(n);
    for(int &x : arr)
        cin >> x;
    sort(all(arr));
    int mn = INT_MAX;
    for(int i = 0; i < n; i++)
    {
        int j = (i + 1) % n;
        int d = (arr[j]-arr[i]+k)%k;
        mn = min(k - d, mn);
        j = (i + n - 1) % n;
        d = (arr[i]-arr[j]+k)%k;
        mn = min(k - d, mn);
    }
    cout<<mn;
}

int main()
{
    FASTIO;
    int t;
    t = 1;
    // cin>>t;
    while(t--)
    {
        cp();
    }
    return 0;
}

Measured memory_bytes: 1024
#![allow(dead_code)]
#![allow(unused_imports)]
use ascii::{AsciiChar, AsciiStr, AsciiString};
use indexmap::IndexMap;
use itertools::*;
use libm::*;
use num::*;
use ordered_float::OrderedFloat;
use permutohedron::LexicalPermutation;
use proconio::marker::{Bytes, Chars};
use proconio::{fastout, input};
use std::cmp::{max, min, Ordering};
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
use std::mem::swap;

fn main() {
    input!(n:isize);
    println!("{}", n / 3);
}


Measured memory_bytes: 2132
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long

priority_queue<int> L;
priority_queue<int, vector<int>, greater<>> R;
ll sz, L_sum, R_sum, B;

signed main() {

    int Q;
    cin >> Q;

    function<void(int)> L_push = [&] (int val) { L_sum += val; L.push(val); ++sz; };
    function<void()>    L_pop  = [&] ()        { L_sum -= L.top(); L.pop(); --sz; };
    function<void(int)> R_push = [&] (int val) { R_sum += val; R.push(val); ++sz; };
    function<void()>    R_pop  = [&] ()        { R_sum -= R.top(); R.pop(); --sz; };

    while (Q--) {
        int q;
        cin >> q;
        if (q == 1) {
            int a, b;
            cin >> a >> b;
            if (sz == 0) {
                L_push(a);
            } else if (sz % 2 == 1) {
                int val = L.top();
                if (val > a) {
                    L_pop();
                    L_push(a);
                    R_push(val);
                } else {
                    R_push(a);
                }
            } else {
                int val = R.top();
                if (a > val) {
                    R_pop();
                    R_push(a);
                    L_push(val);
                } else {
                    L_push(a);
                }
            }
            B += b;
        } else if (q == 2) {
            int L_sz = (sz + 1) / 2;
            int R_sz = sz / 2;
            int mid = L.top();
            ll ans = B;
            ans += R_sum - R_sz * mid;
            ans += L_sz * mid - L_sum;
            cout << mid << ' ' << ans << endl;
        }
    }

}


Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define REP3(i,x,n) for(int i=x; i>(n); i--)
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
int main(){
    char c;
    int index=0;
    string S_inv;
    cin >> S_inv;
    string S = S_inv;
    reverse(S_inv.begin(),S_inv.end());
    index = S.size();
    index--;
    bool tf = true;
    for(int i = 0;i <= index;i++){
        if(S[i]!=S_inv[i]) tf = false;
        if(i <= (index-1)/2){
           // printf("%c%c\n",S[i],S_inv[i+(index+3)/2]);
            if(S[i] != S_inv[i+(index+3)/2]) tf = false;
        }
        if(i <= index && i >= (index+3)/2){
            //printf("%c%c\n",S[i],S_inv[i-(index+3)/2]);
            if(S[i] != S_inv[i-(index+3)/2]) tf = false;
        }
    }
    if(tf) printf("Yes");
    else printf("No");

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>


int main(){
  int d,n,x;

  scanf("%d %d",&d,&n);
  if(n!=100){
    x=pow(100,d)*n;
  printf("%d",x);
}else{
  x=pow(100,d)*(n+1);
  printf("%d",x);
}
  return 0;
}


Measured memory_bytes: 128
#include <stdio.h>

int main(void) {
	int a,b,n;
	int sum;
	int i,j;
	while(1) {
		if(scanf("%d %d %d",&a,&b,&n)==-1)break;
		a-=a/b*b;
		sum=0;
		for(i=1;i<=n;i++) {
			a*=10;
			for(j=9;j>=0;j--) {
				if(b*j<=a)break;
			}
			a-=b*j;
			sum+=j;
		}
		printf("%d\n",sum);
	}
	return 0;
}

Measured memory_bytes: 0
N, L =  (int(j) for j in input().split())  

taste = [L+i-1 for i in range(1,N+1)]

if L > 0:
  print(sum(taste)-taste[0])
elif L + N - 1 <= 0:
  print(sum(taste)-taste[N-1])
else:
  print(sum(taste))


Measured memory_bytes: 3060
from sys import stdin
import heapq

def uf_find(n,p):

    ufl = []

    while p[n] != n:
        ufl.append(n)
        n = p[n]

    for i in ufl:
        p[i] = n

    return n


def uf_union(a,b,p,rank,nums):

    ap = uf_find(a,p)
    bp = uf_find(b,p)

    if ap == bp:
        return True
    else:

        if rank[ap] > rank[bp]:
            p[bp] = ap
            nums[ap] += nums[bp]
        elif rank[ap] < rank[bp]:
            p[ap] = bp
            nums[bp] += nums[ap]
        else:
            p[bp] = ap
            nums[ap] += nums[bp]
            rank[ap] += 1

        return False

N = int(stdin.readline())

xy = []

for i in range(N):

    x,y = map(int,stdin.readline().split())
    x -= 1
    y -= 1
    xy.append((x,y,i))

xy.sort()
q = []

p = [i for i in range(N)]
rank = [0] * N
nums = [1] * N

for x,y,i in xy:

    miny = y
    while len(q) > 0 and q[0] < y:
        ny = heapq.heappop(q)
        uf_union(y,ny,p,rank,nums)
        miny = min(ny,miny,y)
    heapq.heappush(q,miny)

ans = [0] * N

for x,y,i in xy:
    ans[i] = nums[uf_find(y,p)]

print ("\n".join(map(str,ans)))



Measured memory_bytes: 132484
//Comparison

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a/__gcd(a, b)*b)
#define range(a) (a).begin(),(a).end()
#define pb push_back
const int inf = 2147483647;

int main (){
    string s,ss;cin>>s>>ss;
    if(s.size()>ss.size())cout<<"GREATER"<<endl;
    else if(s.size()<ss.size())cout<<"LESS"<<endl;
    else{
        rep(i,0,s.size()){
            if(s[i]>ss[i]){cout<<"GREATER"<<endl;return 0;}
            else if(s[i]<ss[i]){cout<<"LESS"<<endl;return 0;}
        }
        cout<<"EQUAL"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#define _USE_NATH_DEFINES
#include<cstdio>
#include <iostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<complex>
#include <string>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<numeric>
#include<limits>
#include<climits>
#include<cfloat>
#include<functional>
#include<iterator>
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
using namespace std;

int main() {
	int x = 0,n;
	string s;
	cin >> n >> s;
	int ans = 0;
	rep(i, n) {
		if (s[i] == 'I') x += 1;
		if (s[i] == 'D') x -= 1;
		ans = max(ans, x);
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int isprime(int n){
	int i;
	for(i=2;i*i<=n;i++){
		if(n % i==0) return 0;
	}
	return 1;
}
int main(){
	int n,i, max=0;
	while(1){
		  scanf("%d",&n);
		  if(n==0) break;
		  for(i=n;i>=1;i--){
		  	if(isprime(i)==1 && isprime(i-2)==1){
			max=i;
			break;
			}
	    }
	    printf("%d %d\n",max-2,max);
	}
	return 0;
}

Measured memory_bytes: 1808
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

typedef pair<long long int, long long int> P;

int main() {

	long long int n;
	cin >> n;

	long long int a, b;
	P p(0, 0);
	for (long long int i = 0; i < n; i++) {
		cin >> a >> b;
		if (a > p.first) {
			p = P(a, b);
		}
	}

	cout << p.first + p.second << endl;

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(int argc, const char * argv[]) {
    int i, j, k;
    int n, m, l;
    int a[100][100],b[100][100];
    long int s;
    scanf("%d%d%d",&n,&m,&l);
    
    //行列A
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
            scanf("%d",&a[i][j]);
    
    //行列B
    for(i=0;i<m;i++)
        for(j=0;j<l;j++)
            scanf("%d",&b[i][j]);
    
    //行列C
    for(i=0;i<n;i++)
        for(j=0;j<l;j++){
            s = 0;
            for(k=0;k<m;k++)
                s += a[i][k] * b[k][j] ;
            printf("%ld", s);
            if(j+1 == l)
                printf("\n");
            else
                printf(" ");
        }
    return 0;
}



Measured memory_bytes: 2100
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/STACK:256000000")
#define _USE_MATH_DEFINES
#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<algorithm>
#include<cmath>
#include<set>
#include<queue>
#include<sstream>
#include<utility>
#include<map>
#include<ctime>
#include<cstdio>
#include<cassert>
#include<functional>
#include<unordered_map>
#include<deque>
#include<cmath>





using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<char, char> pcc;
typedef pair<double, double> pdd;

#define show(x) cerr << x
#define debug(x) show(#x << ": " << (x) << endl)

const long double PI = 3.14159265358979323846;
const long double eps = 1e-5;
const ll INF = numeric_limits<int>::max();
const ll LINF = numeric_limits<ll>::max();
const ll mod = 1000 * 1000 * 1000 + 7;


void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> r(n);
    for (int i = 0; i < n; ++i) {
        r[i] = (s[i] == 'o');
    }
    r.push_back(r[0]);
    vector<int> x(n + 2);
    for (int m = 0; m < 4; ++m) {
        x[0] = m / 2;
        x[1] = m & 1;
        for (int i = 2; i < n + 2; ++i) {
            x[i] = r[i - 1] ^ x[i - 1] ^ x[i - 2];
        }
        if ((x[0] == x[n]) && (x[1] == x[n + 1])) {
            for (int i = 0; i < n; ++i) {
                if (x[i] == 0)
                    cout << "W";
                else cout << "S";
            }
            cout << endl;
            return;
        }
    }
    cout << -1 << endl;


}


//#define LOCAL

int main() {
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    solve();



#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif	
    return 0;
}


Measured memory_bytes: 1232
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using Graph = vector<vector<int>>;
const int MOD = 1e9 + 7;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    string N;
    cin >> N;

    int nlen = N.length();
    vector<vector<int>> dp(nlen + 5, vector<int>(2, 1e9));
    dp[0][0] = 0;
    for (int i = 0; i < nlen; ++i) {
        int num = N[nlen - i - 1] - '0';
        dp[i + 1][0] = num + min(dp[i][0], dp[i][1] + 1);
        dp[i + 1][1] = 10 - num + min(dp[i][0], dp[i][1] - 1);
    }

    cout << min(dp[nlen][0], dp[nlen][1] + 1) << endl;

    return 0;
}


Measured memory_bytes: 55964
# C - Coloring Colorfully
# https://atcoder.jp/contests/abc124/tasks/abc124_c

S = raw_input()

num0 = 0
num1 = 0
beg0 = '0'
beg1 = '1'

for s in S:
    if s != beg0:
        num0 += 1
    else:
        num1 += 1
    beg0 = '0' if beg0 == '1' else '1'
    beg1 = '0' if beg1 == '1' else '1'

print '{}'.format(min(num0, num1))


Measured memory_bytes: 2692
/*input

*/


//assic value of ('0'-'9') is(48 - 57) and (a-z) is (97-122) and (A-Z) is(65-90) and 32 for space
#include<bits/stdc++.h>
using namespace std;
#define ll          long long
#define pb          push_back
#define pii         pair<ll int,ll int>
#define vpii        vector< pii >
#define vi          vector<ll int>
#define vs			vector< string >
#define vvi         vector< vector< ll > >
#define inf			(ll)1e18
#define all(it,a)   for(auto it=(a).begin();it!=(a).end();it++) 
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define repr(i,a,b) for(ll int i=a;i>b;i--)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define mp          make_pair
#define whatis(x)   cout << #x << " is " << x << "\n";
#define graph(n)    adj(n,vector< ll > () )
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


int solve()
{
	char c;cin>>c;
	cout<<(char)('a'+((c-'a')+1));
	return 0;
}

int main()
{
	auto start = chrono::high_resolution_clock::now();

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	ll test_cases=1;
	//cin>>test_cases;
	while(test_cases--)
		solve();

	auto stop = chrono::high_resolution_clock::now();
	auto duration = chrono::duration_cast<chrono::milliseconds>(stop-start);
	//cout<<"\nduration: "<<(double)duration.count()<<" milliseconds";
}

Measured memory_bytes: 256
import heapq

n,k=map(int,raw_input().split())
a=map(int,raw_input().split())



d={}
for i in a:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
l=d.values()
div=max(0,len(l)-k)
if div==0:
    print 0
    exit()


heapq.heapify(l)

ans=0
while div>0:
    ans+=heapq.heappop(l)
    div-=1
print ans



Measured memory_bytes: 28532
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

struct edge{int t,c,rev;};
typedef vector<edge> ve;
const int INF = 1e8;

int n,m,a,b;
vector<ve> g,tmp;
bool use[210];

void add(int a,int b,int c){
  g[a].push_back((edge){b,c,g[b].size()});
  g[b].push_back((edge){a,0,g[a].size()-1});
}

int dfs(int v,int t,int f){
  if(v==t)return f;
  use[v] = true;
  rep(i,g[v].size()){
    edge &e = g[v][i];
    if(!use[e.t] && e.c>0){
      int d = dfs(e.t,t,min(e.c,f));
      if(d>0){
	e.c -= d;
	g[e.t][e.rev].c += d;
	return d;
      }
    }
  }
  return 0;
}

int max_flow(int s, int t){
  int res = 0;
  while(1){
    memset(use,0,sizeof(use));
    int f = dfs(s,t,INF);
    if(f == 0)return res;
    res += f;
  }
}

int main(){
  cin >> n >> m;
  g.resize(2*n+1);
  rep(i,2*n+1)g[i].clear();

  rep(i,n)add(2*i+1,2*i+2,1);

  rep(i,m){
    cin >> a >> b;
    tmp = g;
    add(2*a,0,1); add(2*b,0,1);

    if(max_flow(2,0)==2)cout << "Yes\n";
    else cout << "No\n";

    g = tmp;
    add(2*a,2*b-1,1); add(2*b,2*a-1,1);
  }
}
    

Measured memory_bytes: 1864
#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<int> g[100005];
int deg[100005],q[100005],dp[100005],head,tail;
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b;cin>>a>>b;
		g[a].push_back(b);
		deg[b]++;
	}
	for(int i=1;i<=n;i++){
		if(!deg[i])
			q[++tail]=i;
	}
	int res=0;
	while(head<tail){
		int x=q[++head];
		res=max(res,dp[x]);
		for(int j=0;j<g[x].size();j++){
			deg[g[x][j]]--;
			dp[g[x][j]]=max(dp[g[x][j]],dp[x]+1);
			if(!deg[g[x][j]])	q[++tail]=g[x][j];
		}
	}
	cout<<res<<endl;
}

Measured memory_bytes: 6912
/*
Author: CNYALI_LK
LANG: C++
PROG: agc1a.cpp
*/
#include<bits/stdc++.h>
#define up(a,b,c) for (int a(b),a##end(c);a<=a##end;++a)
#define down(a,c,b) for (int a(b),a##end(c);a>=a##end;--a)
#define uup(a,c,b) for (int a(b),a##end(c);a<=a##end;++a)
#define udown(a,b,c) for (int a(b),a##end(c);a>=a##end;--a)
#define endl '\n'
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>void chkmin(T &a,T b){a=a<b?a:b;}
template<class T>void chkmax(T &a,T b){a=a>b?a:b;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
int l[128];
int main(){
#ifdef cnyali_lk
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n*2;++i)scanf("%d",l+i);
	sort(l+1,l+n*2+1);
	int sum=0;
	for(int i=1;i<=n;++i)sum+=l[i*2-1];
	printf("%d\n",sum);
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 25;

struct qwq {
    int x, y;
} s[ N ];

bool cmp( qwq a, qwq b ) {
    return a.x - a.y > b.x - b.y;
}

int main( void ) {
    int n;
    cin >> n;
    for( int i = 0; i < n; ++i ) cin >> s[ i ].x;
    for( int i = 0; i < n; ++i ) cin >> s[ i ].y;
    int maxn = 0;
    sort( s, s + n, cmp );
    for( int i = 0; i < n; ++i ) {
        if( s[ i ].x - s[ i ].y > 0 ) maxn += s[ i ].x - s[ i ].y;
    }
    cout << maxn << '\n';
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#define xxx 100100
using namespace std;
struct cmp{
	bool operator()(int &a,int &b){
		return a>b;
	}
};
priority_queue<int,vector<int>,cmp>q;
struct node{
	int from,to;
}p[xxx];
int n,m,k,g=0,x1,y1,x2,y2,p1,p2;

int cg(int x,int y)
{
	if (y==0) return x+1;
	if (x==n) return y+n+1;
	if (y==m) return n-x+n+m+1;
	if (x==0) return m-y+2*n+m+1;
	return -1;
}

bool cmp(node p1,node p2)
{
	return p1.from<p2.from;
}

bool pd()
{
	int t;
	for (int i=1;i<=g;i++)
	{
		while (!q.empty())
		{
			t=q.top();
			if (p[i].from<t) break;
			q.pop();
		}
		if (q.empty())
		{
			q.push(p[i].to);
		}
		else
		{
			t=q.top();
			if (p[i].to>t) return 0;
			q.push(p[i].to);
		}
	}
	return 1;
}

int main()
{
	cin>>n>>m>>k;
	while (k--)
	{
		cin>>x1>>y1>>x2>>y2;
		p1=cg(x1,y1);
		p2=cg(x2,y2);
		//printf(" %d %d\n",p1,p2);
		if (p1>0&&p2>0)
		{
			if (p1>p2) swap(p1,p2);
			p[++g]=(node){p1,p2};
		}
	}
	sort(p+1,p+g+1,cmp);
	if (pd())
		printf("YES\n");
	else
		printf("NO\n");
	return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
 
/*** Template Begins ***/
 
typedef long long    ll;
typedef pair<ll,ll>  pll;
typedef pair<ll, pair<int, int> > plll;
typedef vector<long long>  vll;
typedef vector<pll>  vp;
typedef long double ld;
#define pb           push_back
#define INF          INT_MAX/10
#define F            first
#define S            second
#define mp           make_pair
#define ios          ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define hell         1000000007
// #define h 998244353
#define all(a)       (a).begin(),(a).end()
ll power(ll x, ll y, ll p){ ll res = 1;x = x % p;while (y > 0){ if (y & 1) res = (res*x) % p;y = y>>1;x = (x*x) % p;} return res; } 
 
// Debug //
 
#define trace(x)                 cerr << #x << ": " << x << endl;
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
// #define trace6(a, n,i;b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

// Constants //
 
/*** Template Ends ***/
bool comp(string a,string b)
{
  return a.length()<b.length();
}
void solve()
{
  ll a,b,i;
  cin>>a>>b;
  set<ll> s;
  if(a%2==0)
  {
    s.insert(2);
    while(a%2==0)
      a/=2;
  }
  for(i=3;i<=sqrt(a);i+=2)
  {
    if(a%i==0)
    {
      s.insert(i);
      while(a%i==0)
        a/=i;
    }
  }
  if(a>1)
    s.insert(a);
  ll ans=1;
  if(b%2==0)
  {
    if(s.find(2)!=s.end())
      ans++;
    while(b%2==0)
      b/=2;
  }
  for(i=3;i<=sqrt(b);i+=2)
  {
    if(b%i==0)
    {
      if(s.find(i)!=s.end())
        ans++;
      while(b%i==0)
        b/=i;
    }
  }
  if(b>1)
  {
    if(s.find(b)!=s.end())
      ans++;
  }
  cout<<ans;
}
int main()
{ 
  ios;
  // fxreopen("inputt.txt", "w", stdout);
  ll t;
  // cin >> t;
  t=1;
  while(t--)
    solve();
  return 0;
}

Measured memory_bytes: 256
n = gets.to_i
a = gets.chomp.split(" ").map(&:to_i)
for i in 1..n-1
  a[i] += a[i-1]
end
ans = 10**10
for i in 0..n-2
  ans = [ans,(2*a[i]-a[-1]).abs].min
end
puts ans

Measured memory_bytes: 20484
/** 
 * Dont raise your voice, improve your argument.
 * --Desmond Tutu
 */

#include <bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
typedef long long ll;

#define fori(n) for(ll i=0; i<(n); i++)
#define forn(i, n) for(ll i=0; i<(n); i++)
#define forn3(i, x, n) for(ll i=(x); i<(n); i++)

bool hasDoubleStone(string &s, int a, int c) {
    for(int i=a; i<c; i++) {
        if(s[i]=='#' && s[i-1]=='#')
            return true;
    }
    return false;
}

bool hasTripleFree(string &s, int a, int c) {
    for(int i=a+1; i<c+1; i++) {
        if(s[i]=='.' && s[i-1]=='.' && s[i-2]=='.')
            return true;
    }
    return false;
}

int main() {
cin.tie(nullptr);
std::ios::sync_with_stdio(false);
    int n, a, b, c, d;
    cin>>n>>a>>b>>c>>d;
    string s;
    cin>>s;

    if(hasDoubleStone(s, a, c) || hasDoubleStone(s, b, d)) {
        cout<<"No"<<endl;
        return 0;
    }

    if(c<d) {
        cout<<"Yes"<<endl;
        return 0;
    }

    /* a must overtake b */
    if(hasTripleFree(s, b-1, d)) {
        cout<<"Yes"<<endl;
        return 0;
    }

    cout<<"No"<<endl;
    return 0;
}



Measured memory_bytes: 592
#include<iostream>
using namespace std;

int main(){
 string s;
 int count[26] = {};

 while(cin >> s && (int)s.size() != 0){
  for(int i=0; i<(int)s.size(); i++){
   for(int j=0; j<26; j++){
     if(s[i] == 'a'+j || s[i] == 'A'+j) count[j]++;
   }
  }
 }
 for(int i=0; i<26; i++){
  char c;
  c = 'a'+i;
  cout << c << " : " << count[i] << endl;
 }
}


Measured memory_bytes: 3240
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using boost::multiprecision::cpp_int;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ll,pair<ll, ll>> lpll;
typedef pair<ll, int> pli;
typedef pair<int, int> pii;

#define deg_to_rad(deg) (((deg)/360)*2*PI)

const ll LINF = LLONG_MAX;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;

const ld PI = (acos(-1));
const ld EPS = 0.0000000001;
// cout << fixed << setprecision(10) << middle << endl;

int main() {
    // input, ready
    int N;
    cin >> N;
    int max_ryokan = 0;
    int ans = 0;
    for (int i=0; i<N; i++) {
        int H;
        cin >> H;
        if (H >= max_ryokan) {
            ans++;
            max_ryokan = H;
        }
    }

    // output
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;

int main(){
	int input;
	int abacus[5];
	bool isFirst = true;

	while(cin >> input){
		if(!isFirst) cout << endl;

		for(int i=0; i< 5; i++){
			abacus[4-i] = input% 10;
			input/= 10;
		}

		for(int i=0; i < 5; i++){
			if(abacus[i] < 5) cout << '*';
			else cout << " ";
		}
		cout << endl;

		for(int i=0; i< 5; i++){
			if(abacus[i] < 5){
				cout << " ";
			}
			else{
				cout << "*";
				abacus[i]-= 5;
			}
		}
		cout << endl;

		cout << "=====" << endl;

		for(int i=0; i < 5; i++){
			for(int j=0; j < 5; j++){
				if(abacus[j] == 0) cout << " ";
				else cout << "*";

				abacus[j]--;
			}
			cout << endl;
		}
		isFirst = false;
	}
}

Measured memory_bytes: 1152
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string>
#include <vector>

using namespace std;


/* define */
#define Yes(X) puts ( (X) ? "Yes" : "No")
#define YES(X) puts ( (X) ? "YES" : "NO")
#define FOR(i, a, b) for ( int i = (a); i < (b) ; i++)
#define REP(i, n) for ( int i = 0; i < (n) ; i++)
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))
#define max3(a, b, c) ((max((a), (b)) > (c)) ? max((a), (b)) : (c))
#define min3(a, b, c) ((min((a), (b)) < (c)) ? min((a), (b)) : (c))

/* const */
const int MOD = 1000000007;

/* alias */
typedef long long ll;
typedef unsigned  u;

/* function */
int cmp(const void *a, const void *b) {
	return *(int*)a - *(int*)b;
}
int cmp2(const void *a, const void *b) {
	return *(int*)b - *(int*)a;
}
int gcd(int a, int b) {
	if (b != 0)return gcd(b, a % b);
	return a;
}
ll Lgcd(ll a, ll b) {
	if (b != 0) return Lgcd(b, a % b);
	return a;
}
int lcm(int a, int b) {
	return a / gcd(a, b) * b;
}
ll Llcm(ll a, ll b) {
	return a / Lgcd(a, b) * b;
}

/* main */

ll n, a[100001], b[100000], ans = 0;


int main() {
	cin >> n;
	REP(i, n + 1)cin >> a[i];
	REP(i, n)cin >> b[i];
	REP(i, n) {
		if (a[i] >= b[i]) {
			ans += b[i];
		}
		else {
			ans += a[i];
			b[i] -= a[i];
			if (a[i + 1] >= b[i]) {
				ans += b[i];
				a[i + 1] -= b[i];
				}
			else {
				ans += a[i + 1];
				a[i + 1] = 0;
			}
		}
	}
	cout << ans;
}

Measured memory_bytes: 1792
#include<stdio.h>

int main()
{
	char s1[100][201],s2[100][201],a1[201],a2[201];
	int c,count,i,t,str,count_s1,count_s2;
	int br=0,judge=0,j,k;
	
	while(1)
	{
		j=0;
		k=0;
		count=0;
		count_s1=0;
		count_s2=0;
		
		while((c=getchar())!='\n')
		{
			if(c=='.')
			{
				br=1;
				break;
			}
			if(c=='"')
			{
				judge=1-judge;
				if(judge)
				{
					count_s1++;
					str=0;
				}
				else s1[count_s1-1][str]='\0';
			}
			if(judge)
			{
				s1[count_s1-1][str]=c;
				str++;
			}
			else
			{
				a1[j]=c;
				j++;
			}
		}
		a1[j]='\0';
		if(br) break;
		
		while((c=getchar())!='\n')
		{
			if(c=='"')
			{
				judge=1-judge;
				if(judge)
				{
					count_s2++;
					str=0;
				}
				else s2[count_s2-1][str]='\0';
			}
			if(judge)
			{
				s2[count_s2-1][str]=c;
				str++;
			}
			else
			{
				a2[k]=c;
				k++;
			}
		}
		a2[k]='\0';
		for(int i=0;;i++)
		{
			if(a1[i]=='\0' && a2[i]=='\0') break;
			if(a1[i]!=a2[i])
			{
				count=2;
				break;
			}
		}
		if(count_s1==count_s2 && count==0)
		{
			for(int i=0;i<count_s1;i++)
			{
				//printf("%s\n",s1[i]);
				//printf("%s\n\n",s2[i]);
				for(int t=0;;t++)
				{
					if(s1[i][t]=='\0'&&s2[i][t]=='\0') break;
					if(s1[i][t]!=s2[i][t])
					{
						count++;
						break;
					}
					
				}
			}
		}
		else count=2;
		if(count==0) printf("IDENTICAL\n");
		else if(count==1) printf("CLOSE\n");
		else printf("DIFFERENT\n");
	}
	return 0;
}


Measured memory_bytes: 2108
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for(int i = (a); i < (int)(b); i++)
#define ln(a) cout << (a) << endl
#define debug(a, n) rep(hoge, n) printf("%lld%c", a[hoge], hoge == (n) - 1? '\n' : ' ');
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define INF 1e9
#define LINF 1e18
#define MOD 1000000007
#define EPS 0.00000001

using namespace std;
using ll = long long;
using P = pair<int, int>;
using LP = pair<ll, ll>;

signed main() {
    int h, a;
    cin >> h >> a;
    if(h % a == 0) ln(h / a);
    else ln(h / a + 1);
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
 
using namespace std;

bool prime[200001];

void solve(){
	ll x; cin>>x;
	
	for(int i=2; i<200001; i++){
		if(!prime[i] && (ll)i*i <= 200001){
			for(int j=i; i*j<=200000; j++){
				prime[j*i] = 1;
			}
		}
	}
	for(int i=2; i<=200000; i++){
		if(prime[i] == 0 && i>=x){
			cout<<i; break;
		}
	}


}


int main()
{ 
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//cout<<fixed<<setprecision(12);
	
	int t =1; 
	//cin>>t;

	for(int i=1; i<=t; i++){
		solve();
		cout<<"\n";
	}
	return 0;

}




Measured memory_bytes: 512
N, K = map(int, input().split(' '))
tr = []
for i in range(N):
    tr.append(int(input()))

tr.sort()
INF = float('inf')
ans = INF
for i in range(N-K+1):
    dif = tr[i+K-1] -tr[i]
    if dif < ans:
        ans = dif

print(ans)

Measured memory_bytes: 7384
import fractions

N=int(input())
S=[]
for i in range(N):
    S.append(int(input()))


def koubaisu(a,b):
    return a*b//fractions.gcd(a,b)

ans=1

if N==1:
    print(S[0])
    exit()
elif N==2:
    ans=koubaisu(S[0],S[1])
    print(ans)
    exit()
elif N>2:
    ans=koubaisu(S[0],S[1])
    for i in range(N-2):
        ans=koubaisu(ans,S[i+2])

print(ans)

Measured memory_bytes: 5180
n=int(input())
a=[int(x) for x in input().rstrip().split()]
now=1000
cnt=0
flag=0

for i in range(n-1):
    if flag==1:
        now+=cnt*a[i]
        cnt=0
        flag=0
        if a[i]<a[i+1]:
            cnt=now//a[i]
            now=now-cnt*a[i]
            flag=1
            continue


    if a[i]<a[i+1]:
        cnt=now//a[i]
        now=now-cnt*a[i]
        flag=1

if flag==1:
    now+=cnt*a[n-1]
print(now)

Measured memory_bytes: 9020
#include<cstdio>
typedef long long ll;
char S[45];
ll dp[45][45][45];
int A[45][45], N;
int main() {
	scanf("%d", &N), N <<= 1;
	for(int i=1;i<=N;i++) {
		scanf("%s", S + 1);
		for(int j=1;j<=N;j++)
			A[i][j] = S[j] - '0';
	}
	for(int i=N;i>=2;i--) {
		dp[i][i][i] = 1;
		for(int j=i+2;j<=N;j++)
			for(int k=i+1;k<=j-1;k++) {
				for(int u=i;u<k;u++)
					for(int v=j;v>k;v--)
						if( A[u][v] ) {
							for(int x=u;x<k;x++)
								for(int y=v;y>k;y--)
									dp[i][j][k] += dp[i][x][u]*dp[x+1][y-1][k]*dp[y][j][v];
						}
			}
	}
	ll ans = 0;
	for(int i=2;i<=N;i++)
		if( A[1][i] ) ans += dp[2][N][i];
	printf("%lld\n", ans);
}

Measured memory_bytes: 640
#include<bits/stdc++.h>

using namespace std;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);	
	int n , m;
	cin >> n >> m;
	cout << n *(n - 1)/ 2 + (m - 1)*m/2;
}




Measured memory_bytes: 256
import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = Integer.parseInt(sc.nextLine());
        String[] line = sc.nextLine().split(" ");
        
        int[] targetArray = new int[num];
        for(int i = 0;i < num;i++){
            targetArray[i] = Integer.parseInt(line[i]);         	
        }
        
        int result = 0;
        boolean breakFlg = false;
        
        while(true){
            
            for(int i = 0;i < num ;i++){
                if(targetArray[i] % 2 == 0){
                    targetArray[i]  /= 2;
                }else{
                    breakFlg = true;
                    break;
                }
            }
          	if(breakFlg){
            	break;
            }
			result++;
        }
        System.out.println(result);
    }
}

Measured memory_bytes: 21844
#include<iostream>
using namespace std;

int main()
{
	long long N, M,x;
	cin >> N >> M;
	if (N == 1 && M == 1) {
		cout << 1;
	}
	else if (N >= 2 && M >= 2) {
		cout << (N - 2)*(M - 2) << endl;
	}
	else {
		if (N < M) {
			x = M;
			M = N;
			N = x;
		}
		cout << N - 2 << endl;
	}
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
struct __fastio__{ __fastio__() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } } __fast_io__;
template<class T, class U> bool chmin (T &a, const U &b) { if (a > b) { a = b; return 1; } return 0; }
template<class T, class U> bool chmax (T &a, const U &b) { if (a < b) { a = b; return 1; } return 0; }

int main() {
	long long a, b, c, d;
	std::cin >> a >> b >> c >> d;
	long long ans = std::max(a * c, a * d);
	chmax(ans, b * c);
	chmax(ans, b * d);
	
	std::cout << ans << '\n';
	
	return 0;
}

Measured memory_bytes: 3648
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  string s;
  cin >> s;
  map<string,string> ans = {
    {"ABC","ARC"},
    {"ARC","ABC"},
  };
  cout << ans[s] << endl;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
int main(){

  int X;
  cin >> X;
  
  int num;
  
  int num2;
  
  for(int j = X;j < j + 1e9;++j){
    num = sqrt(j);
    num2 = 0;
    for(int i = 2;i <= num;++i){
      if(j % i == 0){
        num2 = -1;
      }
      else if(!(j % i == 0) && num2 == -1){
        num2 = -1;
      }
      
    }
    if(num2 == 0){
      cout << j << endl;
      return 0;
    }
  }
}

Measured memory_bytes: 256
n,m = map(int,input().split())
a = tuple([tuple(map(int,input().split())) for _ in range(n)])

ok = n
ng = 0
for _ in range(10):
    mid = (ok+ng)//2

    check = True
    inds = [0] * n
    done = [0] * (m+1)
    while(check):
        cnt_max = 0
        cnt = [0] * (m+1)
        for i in range(n):
            ind = inds[i]
            while(done[a[i][ind]] != 0):
                ind += 1
                if(ind == m):
                    check = False
                    break
            if(ind < m):
                inds[i] = ind
                cnt[a[i][ind]] += 1
                cnt_max = max(cnt_max, cnt[a[i][ind]])

        if(cnt_max <= mid):
            break

        for i in range(1,m+1):
            if(cnt[i] > mid):
                done[i] = 1

    if(check):
        ok = mid
    else:
        ng = mid

print(ok)

Measured memory_bytes: 76880
#include <bits/stdc++.h>

#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define out(x) cout << x << endl;
#define all(x) (x).begin(),(x).end()
typedef long long ll;
using namespace std;

int main(){
    map<ll, bool> m;
    int N;
    cin >> N;
    rep(i, N){
        ll tmp;
        cin >> tmp;
        if(m.count(tmp) == 0){
            m[tmp] = true;
        }else{
            m.erase(tmp);
        }
    }
    out(m.size());
    return 0;
}

Measured memory_bytes: 6528
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys

sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    n,c = map(int,input().split())
    d = [list(map(int,input().split())) for i in range(c)]
    cmat = [list(map(int,input().split())) for i in range(n)]
    t = [[0]*c for i in range(3)]
    ans = float("inf")
    for i in range(n):
        for j in range(n):
            t[(i+j)%3][cmat[i][j]-1] += 1
    for i in range(c):
        for j in range(c):
            if i != j:
                for k in range(c):
                    if i != k and j != k:
                        tmpans = 0
                        for l in range(c):
                            tmpans += d[l][i]*t[0][l]+d[l][j]*t[1][l]+d[l][k]*t[2][l]
                        ans = min(ans,tmpans)

    print(ans)
if __name__ == "__main__":
    main() #endline===============================================
    

Measured memory_bytes: 7728
h,w=map(int,input().split())
g=[[*input()] for _ in range(h)]
from collections import *
def bfs(sx,sy):
  d=[[-1]*w for _ in range(h)]
  d[sx][sy]=0
  q=deque([(sx,sy)])
  while q:
    x,y=q.popleft()
    t=d[x][y]+1
    for dx,dy in [(1,0),(0,1),(-1,0),(0,-1)]:
      nx,ny=x+dx,y+dy
      if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and d[nx][ny]<0:
        d[nx][ny]=t
        q.append((nx,ny))
  return d
import numpy as np
a=0
for sx in range(h):
  for sy in range(w):
    if g[sx][sy]=='#': continue
    a=max(a,np.max(bfs(sx,sy)))
print(a)

Measured memory_bytes: 27088
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int n;cin >> n;
vector<int>a(n);
for(int i = 0;i<n;i++) cin >> a[i];
vector<int>dp(n);
dp[1] = abs(a[1]-a[0]);
for(int i = 2;i<n;i++){
    dp[i] = min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]));
}
cout << dp[n-1];
return 0;
}

Measured memory_bytes: 3980
#include <iostream>
#include <queue>
#define int long long
using namespace std;

int n, k;
priority_queue<pair<int , int > , vector<pair<int , int > > , greater<pair<int , int > > > a;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cin >> n >> k;
    for(int i = 1; i <= n; ++i) {
        int x, y;
        cin >> x >> y;
        a.push(make_pair(x, y));
    }
    int tot = 0;
    while(!a.empty()) {
        tot += a.top().second;
        if(tot >= k) {
            cout << a.top().first;
            return 0;
        }
        a.pop();
    }
    return 0;
}

Measured memory_bytes: 2420
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  vector<string> s(N);

  for (int i = 0; i < N; i++) {
    cin >> s.at(i);
  }

  int M;
  cin >> M;
  vector<string> t(M);

  for (int i = 0; i < M; i++) {
    cin >> t.at(i);
  }

  int maximum_amount = 0;
  for (int i = 0; i < N; i++) {
    string word = s.at(i);
    int amount = 0;

    // blue
    for (int j = 0; j < N; j++) {
      if (word == s.at(j)) {
        amount++;
      }
    }
    // red
    for (int j = 0; j < M; j++) {
      if (word == t.at(j)) {
        amount--;
      }
    }

    if (amount > maximum_amount) {
      maximum_amount = amount;
    }
  }

  cout << maximum_amount << endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;

int m, n;
int a[1000];
vector<int> g[1000];
int match[1000];
bool used[1000];

bool dfs(int v){
	used[v] = true;
	for (int u : g[v]){
		int w = match[u];
		if (w < 0 || !used[w] && dfs(w)){
			match[v] = u;
			match[u] = v;
			return true;
		}
	}
	return false;
}

int solve(){
	int res = 0;
	memset(match, -1, sizeof(match));
	for (int v = 0; v < m + n; v++){
		if (match[v] < 0){
			memset(used, 0, sizeof(used));
			if (dfs(v)) res++;
		}
	}
	return res;
}

int main()
{
	while (scanf("%d %d", &m, &n), m){
		fill_n(g, 1000, vector<int>());
		for (int i = 0; i < m + n; i++){
			scanf("%d", a + i);
		}
		
		for (int i = 0; i < m; i++){
			for (int j = m; j < n + m; j++){
				if (__gcd(a[i], a[j]) > 1){
					g[i].push_back(j);
					g[j].push_back(i);
				}
			}
		}
		
		printf("%d\n", solve());
	}
}

Measured memory_bytes: 3368
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N,a,b;
  cin >>N;
  a = 0;
  b = 0;
  vector<int> vec(N);
  for (int i=0;i<N;i++) {
    cin >> vec.at(i);
  }
  sort (vec.begin(),vec.end());
  reverse (vec.begin(),vec.end());
  
  for (int i=0;i<N;i++){
    if (i%2 == 0) {
    a += vec.at(i);
    }
   else { 
    b += vec.at(i);
  }
  } 
  cout << a-b <<endl;
}


Measured memory_bytes: 256
n=int(input())

ts=[]

for i in range(n):
  x,l=map(int,input().split())
  ts.append((x+l,x-l))
  
ts.sort()

#print(ts)
ans=0
old=-10**10
for i,j in ts:
  
  if j>=old:
    old=i
  else:
    ans+=1

print(n-ans)

Measured memory_bytes: 53464
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //GCC5.4.1で配列の範囲外アクセスをエラーにする

//cmdで g++ test.cpp とするとコンパイルできる
//制限1秒なら10^6は余裕 10^7は多分間に合う 10^8はよほど単純でないと厳しい

typedef long long ll; //long long
typedef pair<int,int> pii; //pair<int,int>

const int MOD=1000000007; //10^9+7
const double PI=3.1415926535;

int main(){
    int N;
    cin>>N;
    int hmax;
    cin>>hmax;
    bool ok=true;
    for(int i=1;i<N;i++){
        int h;
        cin>>h;
        hmax=max(hmax,h);
        if(hmax-h>=2){
            ok=false;break;
        }
    }
    cout<<(ok?"Yes":"No")<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;

int main() {
    int k, n;
    cin >> k >> n;
    int a[n];
    rep(i, n) cin >> a[i];

    int ans = a[n - 1] - a[0];
    rep(i, n - 1) { ans = min(ans, k - (a[i + 1] - a[i])); }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
L, R = map(int,input().split())
if R-L >= 2018:
    ans = 0
elif L%2019 > R%2019:
    ans = 0
else:
    ans = 2018
    for i in range(L,R):
        for j in range(i+1,R+1):
            ans = min(ans, (i*j)%2019)
print(ans)




Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;

typedef long long ll;

int main() {
    int D;
    cin >> D;
    vector<int> c(26), t(D);
    rep(i, 26) cin >> c[i];
    vector<vector<int>> s(D, vector<int>(26)), last(D + 1, vector<int>(26, 0));
    rep(i, D) rep(j, 26) cin >> s[i][j];
    rep(i, D) cout << "1\n";
}

Measured memory_bytes: 3720
n,k = map(int,input().split())
dp = list(map(int,input().split()))
if k > 1000:
  ans = [n for _ in range(n)]
  print(*ans)
else:
  for i in range(k):
    ndp = [0 for _ in range(n)]
    for j in range(n):
      if j-dp[j] < 0:
        ndp[0] += 1
      else:
        ndp[j-dp[j]] += 1
      if j+dp[j]+1 < n:
        ndp[j+dp[j]+1] -= 1
    for j in range(1,n):
      ndp[j] += ndp[j-1]
    dp = ndp[:]
  print(*dp)


Measured memory_bytes: 170824
//Don't have to see. start------------------------------------------
var read = require('readline').createInterface({
  input: process.stdin, output: process.stdout
});
var obj; var inLine = [];
read.on('line', function(input){inLine.push(input);});
read.on('close', function(){
  obj = init(inLine);
  console.error('\n');
  var start = Date.now();
  Main();
  var end = Date.now() - start;
  myerr('time : ' + end + 'ms');
  myerr('memory : ' + Math.round(process.memoryUsage().heapTotal / 1024) + 'KB');
});
function makeClone(obj){return (obj instanceof Set) ? new Set(Array.from(obj)) : JSON.parse(JSON.stringify(obj));}
function nextInt(){return myconv(next(),1);} function nextStrArray(){return myconv(next(),2);}
function nextIntArray(){return myconv(next(),4);} function nextCharArray(){return myconv(next(),6);}
function next(){return obj.next();} function hasNext(){return obj.hasNext();}
function init(input){  
  return {
    list : input, index : 0, max : input.length,
    hasNext : function(){return (this.index < this.max);},
    next : function(){if(this.hasNext()){return this.list[this.index++];}else{throw 'ArrayIndexOutOfBoundsException ‚There is no more input';}}
  };
}
function myout(s){console.log(s);}
function myerr(s){console.error('debug:' + require('util').inspect(s,false,null));}
//param "no" is
//unknown or outlier : return i. 1: parseInt.
//2: split space. 4: split space and parseInt.
//6: split 1 character. 7: split 1 character and parseInt.
//8: join space. 9: join nextline. 0: join no character.
function myconv(i,no){try{switch(no){case 1:return parseInt(i);case 2:return i.split(' ');case 4:return i.split(' ').map(Number);case 6:return i.split('');case 7:return i.split('').map(Number);case 8:return i.join(' ');case 9:return i.join('\n');case 0:return i.join('');default:return i;}}catch(e){return i;}}

//Don't have to see. end------------------------------------------
function Main(){
  var one = nextIntArray();
  var N = one[0];
  var K = one[1];
  var mod = 1000000007;
  var output = 0;
  for(var i = K; i <= N + 1; i++){
    var min = i * (i - 1) / 2;
    var max = N * i - min;
    output += max - min + 1;
    output %= mod;
  }
  myout(output);
}


Measured memory_bytes: 33932