akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cassert>
#include <functional>

using namespace std;

#define LOG(...) printf(__VA_ARGS__)
//#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define CLR(a) memset((a), 0 ,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int dx[] = { -1, 0, 1, 0 }; const int dy[] = { 0, 1, 0, -1 };

struct UnionFind {
	vector<int> v;
	UnionFind(int n) : v(n)  { for (int i = 0; i < n; i++) v[i] = i; }
	int  find(int x)         { return v[x] == x ? x : v[x] = find(v[x]); }
	void unite(int x, int y) { v[find(x)] = find(y); }
};

int main() {
	int n;
	string s;
	cin >> n;
	if (n % 2 == 1) {
		cout << "NO" << endl;
		return 0;
	}
	int cnt = 0;
	REP(i, n) {
		cin >> s;
		if (s == "A")
			cnt++;
		else
			cnt--;
		if (cnt < 0) {
			cout << "NO" << endl;
			return 0;
		}
	}
	if (cnt == 0) 
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}

Measured memory_bytes: 3120
#include "bits/stdc++.h"
using namespace std;
typedef long long int lint;
typedef pair<lint, lint> plint;
typedef pair<double long, double long> pld;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for(lint i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(lint i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
template<typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2>& l, const pair<T1, T2>& r) { return make_pair(l.first + r.first, l.second + r.second); }
template<typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2>& l, const pair<T1, T2>& r) { return make_pair(l.first - r.first, l.second - r.second); }
const lint MOD = 1e9 + 7, INF = 1e18;

lint N, M_a, M_b;
lint a[40], b[40], c[40];
lint dp[41][401][401];
int main() {
	cin >> N >> M_a >> M_b;
	REP(i, N) {
		cin >> a[i] >> b[i] >> c[i];
	}
	REP(i, N + 1) {
		REP(j, 401) {
			REP(k, 401) {
				dp[i][j][k] = INF;
			}
		}
	}
	dp[0][0][0] = 0;
	REP(i, N) {
		REP(j, 401) {
			REP(k, 401) {
				chmin(dp[i + 1][j][k], dp[i][j][k]);
				if (j + a[i] <= 400 && k + b[i] <= 400) {
					chmin(dp[i + 1][j + a[i]][k + b[i]], dp[i][j][k] + c[i]);
				}
			}
		}
	}
	lint curr_a = M_a, curr_b = M_b;
	lint minv = INF;
	while (curr_a <= 400 && curr_b <= 400) {
		chmin(minv, dp[N][curr_a][curr_b]);
		curr_a += M_a;
		curr_b += M_b;
	}
	if (minv == INF) cout << -1 << endl;
	else cout << minv << endl;
}

Measured memory_bytes: 55140
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = 1; i < (int)(n + 1); i++)
// vector<vector<int>> A(3, vector<int>(4));
int main() {
  	ll N,K;
    cin>>N>>K;
    vector<pair<ll,ll>>A(N);
    rep(i,N){
        cin>>A[i].first;
        cin>>A[i].second;
    }
    sort(A.begin(),A.end());
    rep(i,N){
        K-=A[i].second;
        if(K<=0){
            cout<<A[i].first<<endl;
          	i+=K;
          	break;
        }
    }
}


Measured memory_bytes: 4768
#include<cstdio>
#include<algorithm>
#include<functional>
using namespace std;
int main(void)
{
	int i,flg;
	long long int p[100000],q[100000],max,max1,n,s,max2,max3;
	scanf("%lld",&n);
	while(n!=0){
		max=0;
		max1=0;
		max2=0;
		max3=0;
		flg=0;
		for(i=0;i<n;i++) {
			scanf("%lld",&p[i]);
			max+=p[i];
			max1+=p[i];
		}
		max*=n;
		s=n-1;
		for(i=0;i<s;i++) {
			scanf("%lld",&q[i]);
		}
		sort(q,q+s,greater<long long int>());
		for(i=0;i<s;i++){
			n--;
			max1+=q[i];
			max3=max1*n;
			if(max<max3){
				if(max2<max3){
					max2=max3;
					flg=1;
				}
			}
		}
		if(flg==1){
			printf("%lld\n",max2);
		}
		else {
			printf("%lld\n",max);
		}
		scanf("%lld",&n);
	}
	return 0;
}

Measured memory_bytes: 2076
# import numpy as np
# import scipy as sp
# print(a,b,c,sep="") # 半角スペースなしで出力(abc)
# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 文字列の二次元配列入力
# s = [list(map(int, input().split())) for i in range(n)] # 数値の二次元配列入力
# import sys ; sys.exit() # プログラム終了
# from copy import deepcopy ; b=deepcopy(a)
# chr(ord('a') + 1)
# s.sort(key=lambda x: x[1], reverse=False) # 2番目の要素で昇順にソート（Trueなら降順）
#

a, b, c, d = map(int, input().split())

if abs(a-c) <= d or (abs(a-b) <= d and abs(b-c) <= d):
    print('Yes')
else:
    print('No')


Measured memory_bytes: 38384
use std::io::*;
use std::str::FromStr;

fn main() {
    let n: usize = read();
    let a: Vec<usize> = (0..n).map(|_| read()).collect();

    let mut b: Vec<usize> = vec![0; n];
    let mut sum: Vec<usize> = vec![0; n];
    for i in (0..n).rev() {
        let ai = a[i] % 2;
        let sumi = sum[i] % 2;
        if ai == sumi {
            b[i] = 0;
        } else {
            b[i] = 1;
        }
        let mut j = 1;
        while j * j <= (i+1) {
            if (i+1) % j == 0 {
                sum[j-1] += b[i];
                if j != (i+1)/j {
                    sum[(i+1)/j-1] += b[i];
                }
            }
            j += 1;
        }
    }
    let mut cnt = 0;
    for i in 0..n {
        if b[i] > 0 {
            cnt += 1;
        }
    }
    println!("{}", cnt);
    for i in 0..n {
        if b[i] > 0 {
            println!("{}", i+1);
        }
    }
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


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

vector<long long int> a(51), p(51);

long long int rec(long long int n, long long int x){
    // terminal case
    if(n == 0){
        if(x <= 0) return 0;
        else return 1;
    }

    else if(x <= 1 + a[n-1]) return rec(n-1,x-1);
    else return p[n-1] + 1 + rec(n-1,x-a[n-1]-2);
}

int main(){
    long long int n, x;
    cin >> n >> x;

    a[0] = 1;
    p[0] = 1;
    for(int i=1; i<n+1; i++){
        a[i] = 2 * a[i-1] + 3;
        p[i] = 2 * p[i-1] + 1;
    }

    cout << rec(n, x) << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<queue>

using namespace std;

void Rabin_Karp_search( const string &P,const string &T, int base, int hash_m)
{
    int m = P.length();
    int n = T.length();
    int i, j,p = 0,t = 0,h = 1;

    for (i = 0; i < m-1; i++)
        h = (h*base)%hash_m;
    for (i = 0; i < m; i++)
    {
        p = (base*p + P[i])%hash_m;
        t = (base*t + T[i])%hash_m;
    }
    for (i = 0; i <= n - m; i++)
    {
        if ( p == t )
        {
            for (j = 0; j < m; j++)
               if (T[i+j] != P[j])
				   break;
            if (j == m)  // if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1]
               cout<<i<<endl;
        }
        if ( i < n-m )///不是最后一个
        {
            t = (base*(t - T[i]*h) + T[i+m])%hash_m;
            if(t < 0)
              t = (t + hash_m);
        }
    }
}
int main()
{
    string T,P;
    cin>>T>>P;
    Rabin_Karp_search(P,T,131,1001);
    return 0;
}



Measured memory_bytes: 3220
#include<cstdlib>
#include<vector>
#include<string>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
#include<stack>
#include<cstdio>
#include<iostream>
#include<vector>
#define MAXN 1000
using namespace std;
typedef long long ll;
ll data[300000]={0};
int main()
{
	ios::sync_with_stdio(false);
//	freopen("../in", "r", stdin);
//	freopen("../out", "w", stdout);
	ll m,n,k;
	ll temp;
	cin>>m>>n>>k;
	for(ll i=0;i<k;i++)
	{
		cin>>temp;
		data[temp-1]++;
	}
	for(ll i=0;i<m;i++)
	{
		if(n>(k-data[i]))
			cout<<"Yes"<<endl;
		else
			cout<<"No"<<endl;
	}
	return 0;
}

Measured memory_bytes: 1408
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main{
    public static Node root;

    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; i++){
            String[] input = br.readLine().split(" ");
            if(input.length == 2){
                if(input[0].charAt(0) == 'i'){
                    insert(Integer.parseInt(input[1]));
                }else{
                    Node target = find(root, Integer.parseInt(input[1]));
                    if(target != null) System.out.print("yes\n");
                    else System.out.print("no\n");
                }
            }else{
                inorder(root);
                System.out.println("");
                preorder(root);
                System.out.println("");
            }
        }
    }
 public static void insert(int key){
        Node x_parent = null;
        Node x = root;
        Node z = new Node(key);
         while(x != null){
             x_parent = x;
             if(z.key < x.key){
                 x = x.left;
             }else{
                 x = x.right;
             }
         }
         z.parent = x_parent;

         if(x_parent == null){
             root = z;
         }else{
            if(z.key < x_parent.key){
                x_parent.left = z;
            }else{
                x_parent.right = z;
            }
        }
    }

    public static Node find(Node node, int key){
        while(node != null && key != node.key){
            if(key < node.key) node = node.left;
            else node = node.right;
        }
        return node;
    }

    public static void inorder(Node node){
        if(node == null)return;
        inorder(node.left);
        System.out.print(" " + node.key);
        inorder(node.right);
    }
public static void preorder(Node node){
        if(node == null)return;
        System.out.print(" " + node.key);
        preorder(node.left);
        preorder(node.right);
    }


}

class Node{
    int key;
    Node right, left, parent;

    Node(int key){
        this.key = key;
        this.right = null; this.left = null; this.parent = null;
    }
}

Measured memory_bytes: 132520
N = int(input())
A = [int(input()) for i in range(N)]

A_max = max(A)

if A.count(A_max) > 1:
    A_second_max = A_max
else:
    A_second_max = max([0 if i == A_max else i for i in A])

for j in A:
    if j == A_max:
        print(A_second_max)
    else:
        print(A_max)

Measured memory_bytes: 12580
def SieveOfEratosthenes(n): 
    prime = [True for i in range(10**6 + 1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * 2, 10**6 + 1, p): 
                if prime[i]:    prime[i] = False
        p += 1
    prime[0], prime[1] = False, False
    count = 1
    while(True):
        if prime[p] and p>=n:
            print(p);    break
        p += 1
            
n = int(input())
SieveOfEratosthenes(n)

Measured memory_bytes: 17036
#include <iostream>
#define llint long long
#define mod 1000000007

using namespace std;

llint N, K;
llint dp[105][10005];
llint beki[105];

int main(void)
{
	cin >> N >> K;
	dp[N+1][0] = 1;
	
	beki[0] = 1;
	for(int i = 1; i <= N; i++) beki[i] = beki[i-1] * (K+1) % mod;
	
	int nj;
	for(llint i = N+1; i > 1; i--){
		for(int j = 0; j <= N*K; j++){
			if(dp[i][j] == 0) break;
			for(int k = 0; k <= min(i-1, K); k++){
				nj = j + (j+k)/(i-1);
				dp[i-1][nj] += dp[i][j];
				dp[i-1][nj] %= mod;
			}
			for(int k = i; k <= K; k++){
				dp[i-1][j] += dp[i][j];
				dp[i-1][j] %= mod;
			}
		}
	}
	
	llint ans = 0;
	for(int i = 1; i <= N; i++){
		llint tmp = 0;
		for(int j = 0; j <= N*K; j++){
			if(dp[i+1][j] == 0) break;
			for(int k = 0; k <= K; k++){
				if(k > i) tmp += (k+j) * dp[i+1][j] % mod, tmp %= mod;
				else tmp += (k+j)%i * dp[i+1][j] % mod, tmp %= mod;
			}
		}
		tmp *= beki[i-1], tmp %= mod;
		ans += tmp, ans %= mod;
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 6656
#include<cstdio>
#include<algorithm>
using namespace std;
struct A{
	int no;
	int num;
}a[200001];
bool cmp(A a,A b)
{
	return a.num>b.num;
}
int main()
{
	int n,k;
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++){
		a[i].no=i;
	}
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		a[x].num++;
	}
	sort(a+1,a+1+n,cmp);
	int sum=0,ans=0;
	for(int i=1;i<=n;i++){
		if(a[i].num){
			if(sum<k){
				sum++;
			}else{
				ans+=a[i].num;
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1664
#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <cassert>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
const double EPS = 1e-10;
const double PI  = acos(-1.0);


const int MAX_N=100;
int par[MAX_N];
int myrank[MAX_N];

void init(int n){
	for(int i=0;i<n;i++){
		par[i]=i;
		myrank[i]=0;
	}
}

int find(int x){
	if(par[x]==x){
		return x;
	}else{
		return par[x]=find(par[x]);
	}
}

void unite(int x,int y){
	x=find(x);
	y=find(y);
	if(x==y)return;

	if(myrank[x]<myrank[y]){
		par[x]=y;
	}else{
		par[y]=x;
		if(myrank[x]==myrank[y])myrank[x]++;
	}
}

bool same(int x,int y){
	return find(x)==find(y);
}

struct edge{
	int from,to,cost;
	edge(int from,int to,int cost):from(from),to(to),cost(cost){}
	bool operator<(const edge &other)const{
		return cost<other.cost;
	}
};
int main(){
	int n,m;
	while(cin>>n>>m,n|m){
		vector<edge>edges;
		REP(i,m){
			int a,b,w;
			cin>>a>>b>>w;
			a--;b--;
			edges.push_back(edge(a,b,w));
		}
		sort(ALL(edges));
		int ans=INT_MAX;
		REP(i,edges.size()){
			init(n);
			int cost=0;
			int cnt=0;
			FOR(j,i,edges.size()){
				if(cnt==n-1)break;
				if(!same(edges[j].from,edges[j].to)){
					unite(edges[j].from,edges[j].to);
					cost=edges[j].cost-edges[i].cost;
					cnt++;
				}
			}
			if(cnt==n-1){
				ans=min(ans,cost);
			}
		}
		cout<<(ans==INT_MAX?-1:ans)<<endl;
	}
}

Measured memory_bytes: 1328
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.TreeMap;
public class Main {
	public static void main(String[] args){
		int i, q, order;
		String key, key2, str = "";
		TreeMap<String, Integer> tm = new TreeMap<String, Integer>();
		try (Scanner sc = new Scanner(System.in)) {
			q = sc.nextInt();
			for(i = 0; i < q; i++) {
				order = sc.nextInt();
				key = sc.next();
				switch(order) {
				case 0 :
					tm.put(key, sc.nextInt());
					break;
				case 1 :
					if(tm.get(key) == null) {
						System.out.println(0);
					}else {
						System.out.println(tm.get(key));
					}
					break;
				case 2 :
					tm.remove(key);
					break;
				case 3 :
					key2 = sc.next();
					for(Entry<String, Integer> output : tm.subMap(key, true, key2, true).entrySet()) {
						System.out.println(output.getKey() + " " + output.getValue());
					}
					break;
				}
			}
		}
	}
}



Measured memory_bytes: 200352
#include <iostream>
#define INF ((1 << 30) - 1)
using namespace std;
typedef long long Int;

Int n;
Int h[110000], dp[110000];

int main() {
  cin >> n;
  for (int i = 0; i < n; i++) cin >> h[i];

  for (int i = 1; i < n; i++) dp[i] = INF;
  dp[0] = 0;
  for (int i = 0; i < n; i++) {
    dp[i + 1] = min(dp[i] + abs(h[i + 1] - h[i]), dp[i + 1]);
    dp[i + 2] = min(dp[i] + abs(h[i + 2] - h[i]), dp[i + 2]);
  }
  cout << dp[n - 1] << endl;
  return 0;
}

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

int main() {
	int n;
  	cin>>n;
  
  vector<int> c(50);
  vector<int> v(50);
  
  rep(i,n)cin>>c[i];
  rep(j,n)cin>>v[j];
  
  int vc=0;
  
  rep(k,n){
  	if(c[k]>v[k]){
    	vc+=c[k]-v[k];
    }
  }
  
  cout<<vc<<endl;
  
}

Measured memory_bytes: 3596
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;

public class Main{
	public static void main(String[] args){

		InputStreamReader ISR = new InputStreamReader(System.in);
		BufferedReader BR = new BufferedReader(ISR);
		//入力
		try{
			String strTime = BR.readLine();

			//int型に変換
			int intTime = Integer.parseInt(strTime);
			//60秒(1分)で割り切れなかったものが秒
			int intSecond =intTime % 60;
			//3600秒(1時間)の余りで、60秒で切りきれたものが分
			int intMinute = (intTime % 3600)/60;
			//3600(1時間)で割り切れたものが時
			int intHour = intTime / 3600;

			System.out.println(intHour + ":" + intMinute +":" + intSecond);
		}catch(IOException e){
			System.out.println(e);
		}
	}	
}



Measured memory_bytes: 24444
#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>




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 int INF = numeric_limits<int>::max();
const ll LINF = numeric_limits<ll>::max();
const ll mod = 1000 * 1000 * 1000 + 7;

    

void solve() {
    int n;
    int k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int res = abs(a[0]) + abs(a[n - 1]) + a[n - 1] - a[0];
    for (int i = 0; i < n; ++i) {
        int j = i + k - 1;
        if (j >= n)
            break;
        res = min(res, a[j] - a[i] + min(abs(a[i]), abs(a[j])));
    }
    cout << res << endl;
    


}

//#define LOCAL

int main() {
    ios_base::sync_with_stdio(0);
#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: 640
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long

const int N = 1e5 + 9;
vector<int> vec[N];
vector<int> sign(N, -1);
int n, m;

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n >> m;
	for(int i = 0; i < m; i ++) {
		int x, y; cin >> x >> y;
		vec[x].push_back(y);
		vec[y].push_back(x);
	}
	sign[1] = 1;
	queue<int> q;
	q.push(1);
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(int v : vec[u]) {
			if(sign[v] == -1) {
				q.push(v);
				sign[v] = u;
			}
		}
	}
	for(int i = 1; i <= n; i ++) {
		if(sign[i] == -1) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	for(int i = 2; i <= n; i ++)
		cout << sign[i] << endl;


	return 0;
}

Measured memory_bytes: 12888
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<char> vchar;
typedef vector<int> vint;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef vector<vector<int>> vvint;
typedef vector<vector<char>> vvchar;
#define vsort(v) sort((v).begin(), (v).end())
#define vrsort(v) sort((v).rbegin(), (v).rend())
#define vreverse(v) reverse((v).begin(), (v).end())
#define pb(a) push_back(a)
#define INF 2000000009
#define MOD 1000000007
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  //input
  int n,a,b;cin>>n>>a>>b;
  cout<<min(n*a,b)<<endl;
  //caricurate
  //output
}

Measured memory_bytes: 256
#include <cstdio>
using namespace std;
int main(){
  char c11,c12,c13,c21,c22,c23;
  scanf("%c %c %c %c %c %c",&c11,&c12,&c13,&c21,&c22,&c23);
  if(c11==c23&&c12==c22&&c13==c21) printf("YES\n");
  else printf("NO\n");
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

template <class Abel> struct BIT {
    vector<Abel> dat[2];
    Abel UNITY_SUM = 0;                     // to be set
    
    /* [1, n] */
    BIT(int n) { init(n); }
    void init(int n) { for (int iter = 0; iter < 2; ++iter) dat[iter].assign(n + 1, UNITY_SUM); }
    
    /* a, b are 1-indexed, [a, b) */
    inline void sub_add(int p, int a, Abel x) {
        for (int i = a; i < (int)dat[p].size(); i += i & -i)
            dat[p][i] = dat[p][i] + x;
    }
    inline void add(int a, int b, Abel x) {
        sub_add(0, a, x * -(a - 1)); sub_add(1, a, x); sub_add(0, b, x * (b - 1)); sub_add(1, b, x * (-1));
    }
    
    /* a is 1-indexed, [a, b) */
    inline Abel sub_sum(int p, int a) {
        Abel res = UNITY_SUM;
        for (int i = a; i > 0; i -= i & -i) res = res + dat[p][i];
        return res;
    }
    inline Abel sum(int a, int b) {
        return sub_sum(0, b - 1) + sub_sum(1, b - 1) * (b - 1) - sub_sum(0, a - 1) - sub_sum(1, a - 1) * (a - 1);
    }
    
    /* debug */
    void print() {
        for (int i = 1; i < (int)dat[0].size(); ++i) cout << sum(i, i + 1) << ",";
        cout << endl;
    }
};

int main() {
    int N; cin >> N;
    int Q; cin >> Q;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    vector<int> lefts(Q), rights(Q), ids(Q);
    for (int i = 0; i < Q; ++i) {
        cin >> lefts[i] >> rights[i];
        rights[i];
        --lefts[i];
        ids[i] = i;
    }
    sort(ids.begin(), ids.end(), [&](int i, int j) {
            return rights[i] < rights[j];});

    BIT<int> bit(N+5);
    vector<int> prev(1100000, -1);
    vector<int> res(Q, 0);
    int r = 0;
    for (auto i : ids) {
        for (; r < rights[i]; ++r) {
            bit.add(prev[a[r]]+2, r+2, 1);
            prev[a[r]] = r;
        }
        int tmp = bit.sum(lefts[i]+1, lefts[i]+2);
        res[i] = max(res[i], tmp);
    }
    for (int i = 0; i < Q; ++i) cout << res[i] << endl;
}

Measured memory_bytes: 21728
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
typedef long long ll;
const ll longinf=1LL<<60;
const ll P=1000000007;
using namespace std;

ll f[120000];
int flag[120000];
int af[120000];
int n,m,x;

ll dp(int i)
{
    if (i<0) return 0;
    if (i==0) return 1;
    if (af[i]) return 0;
    if (flag[i]) return f[i];
    flag[i]=1;
    f[i] = (dp(i-1)+dp(i-2))%P;
    return f[i];
}

int main()
{
    cin>>n;
    cin>>m;
    for (int i=1; i<=m; ++i)
    {
        cin>>x;
        af[x]=1;
    }
    cout<<dp(n)<<endl;
    return 0;
}



Measured memory_bytes: 4864
#include <iostream>
#include <vector>
#include <algorithm>
// #include <string>
// #include <map>
// #include <set>
// #include <cmath>

#define INF 10000

using namespace std;
// typedef unsigned long long ull;

template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "[";
    for (const auto i : v) {
        os << i << " ";
    }
    os << "]";
    return os;
}

int main(int argc, char const *argv[]) {
    int N, Ma, Mb;
    cin >> N >> Ma >> Mb;

    vector<int> a(N), b(N), c(N);
    for (int i = 0; i < N; ++i) {
        cin >> a[i] >> b[i] >> c[i];
    }

    int a_max = *max_element(a.begin(), a.end());
    int b_max = *max_element(b.begin(), b.end());
    // cout << a_max << " " << b_max << endl;

    vector<vector<vector<int>>> dp(N+1);
    for (int i = 0; i <= N; ++i) {
        dp[i].resize(a_max * N + 1);
        for (int j = 0; j <= a_max * N; ++j) {
            dp[i][j].resize(b_max * N + 1, INF);
        }
    }

    dp[0][0][0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= a_max * N; ++j) {
            for (int k = 0; k <= b_max * N; ++k) {
                if (j >= a[i] && k >= b[i]) {
                    dp[i+1][j][k] = min(dp[i][j][k], dp[i][j-a[i]][k-b[i]] + c[i]);
                } else {
                    dp[i+1][j][k] = dp[i][j][k];
                }
            }
        }
    }

    int r = 1;
    int ans = INF;
    while (true) {
        int ma = Ma * r;
        int mb = Mb * r;
        if (ma > a_max * N || mb > b_max * N) {
            break;
        }
        ans = min(ans, dp[N][ma][mb]);
        r += 1;
    }

    if (ans == INF) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 26624
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    String[] data = br.readLine().split(" ");
    br.close();
    long[] a = new long[n];
    for(int i = 0; i < n; i++){
      a[i] = Long.parseLong(data[i]);
    }
    long ans = 0;
    long sum = 0;
    long mod = 1_000_000_007;
    for(int i = n - 1; i > 0; i--){
      sum += a[i];
      sum %= mod;
      ans += + a[i - 1] * sum;
      ans %= mod;
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 62336
#include <bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
using ar=array<ull,26>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,a,n) for(int i=a;i<n;i++)
int main(){
	string s1,s2;
	ar ht; ht[0]=1;
	rep(i,25) ht[i+1]=ht[i]*10007;
	
	while(cin>>s1>>s2){
		if(s1.size()>s2.size()) swap(s1,s2);
		int n1=s1.size(), n2=s2.size();
		
		unordered_set<ull> list1;
		for(int l=n1;l>=1;l--){
			list1.clear();
			ull tmp=0;
			rep(i,n1) {
				tmp+=ht[s1[i]-'a'];
				if(i>=l) tmp-=ht[s1[i-l]-'a'];
				if(i>=l-1) list1.insert(tmp);
			}
			tmp=0;
			rep(i,n2){
				tmp+=ht[s2[i]-'a'];
				if(i>=l) tmp-=ht[s2[i-l]-'a'];
				if(i>=l-1) {
					if(list1.find(tmp) != list1.end()){
						cout<<l<<endl;
						goto end;
					}
				}
			}
		}
		cout<<0<<endl;
		end: ;
	}
	return 0;
}



Measured memory_bytes: 3328
open Core;;

let mm = 1000000007;;

let () = 
  let a =
    let _ = In_channel.(input_line stdin) in
    List.map ~f:Int.of_string (String.split ~on:' ' (In_channel.(input_line_exn stdin))) in
  let (_, res) = List.fold ~init:(0,0) ~f:(fun (s,r) x -> ((s + x) mod mm, (r + s * x) mod mm)) a in
  printf "%d\n" res
;;




Measured memory_bytes: 34936
#include <iostream>

using namespace std;

int main(){
    int w=0,a=0,b=0;
    cin >> w >> a >> b;
    if(a<=b){
        cout << (b-(a+w)<0?0:b-(a+w)) << endl;
    }else{
        cout << (a-(b+w)<0?0:a-(b+w)) << endl;
    }
    return 0;
}


Measured memory_bytes: 256
N = int(input())
S = [input() for _ in range(N)]
C0 = 0
C1 = 0
C2 = 0
C3 = 0
for i in range(N):
  if S[i] == "AC": C0 += 1
  elif S[i] == "WA": C1 += 1
  elif S[i] == "TLE": C2 += 1
  else: C3 += 1
print("AC x "+ str(C0))
print("WA x "+ str(C1))
print("TLE x "+ str(C2))
print("RE x "+ str(C3))


Measured memory_bytes: 82592
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  auto is_valid = [&] (int x) {
    for (int i = 0; i < n; i++) if (a[i] != x && a[i] + 1 != x) return false;
    int alone = 0;
    for (int i = 0; i < n; i++) if (a[i] + 1 == x) alone++;
    int paired = n - alone;
    if (paired == 1) return false;
    return (alone + (paired > 0)) <= x && x <= (alone + paired / 2);
  };
  for (int x : {a[0], a[0] + 1}) if (is_valid(x)) {
    cout << "Yes\n";
    return 0;
  }
  cout << "No\n";
  return 0;
}

Measured memory_bytes: 640
N=int(input())
a=map(int,input().split())
odd=[]
even=[]
adj=[]
for i in a:
    if i%2:odd.append(i)
    else:even.append(i)
    if i%4==0:adj.append(i)
L=len(adj)-len(odd)
if L+1>0:
    print("Yes")
    exit()
if L==-1:
    print(["Yes","No"][len(even)-len(adj)>0])
else:print("No")

Measured memory_bytes: 16040
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include<limits.h>
#include<iomanip>
#define rep(i, n) for(int i = 0; i < n; i++)
#define rrep(i, n) for(int i = n-1; i >= 0; i--)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define RALL(v) v.rbegin(),v.rend()
#define check(v) rep(i,v.size()) cout << v[i] << " ";\
cout << endl
const long long LLINF = 1LL<<60;
const int INF = 1e9;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
typedef long long ll;
#define pint pair<int,int>
using namespace std;
//オーバーフローに気をつけろよおおおおおお
//確認忘れるなよおおおおおお

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    vector<pint> v[15];
    rep(i,n) {
        int a; cin >> a;
        rep(j,a) {
            int a2, b2; cin >> a2 >> b2;
            a2--;
            v[i].push_back({a2,b2});
        }
    }
    int lis[16];
    int ans = 0;
    for(int bit = 0; bit < (1<<n); bit++) {
        int cnt = 0;
        rep(i,16) lis[i] = INF;
        bool flag = true;
        for(int i = 0; i < n; i++) {
            if(bit & (1<<i)) {
                lis[i] = 1;
                if(lis[i]==0) flag = false;
                rep(j,v[i].size()) {
                    if((bit>>v[i][j].first & 1)^v[i][j].second) flag = false; 
                }
                cnt++;
            }
        }
        if(flag) ans = max(ans,cnt);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);
		int a=scan.nextInt(),b=scan.nextInt(),k=scan.nextInt(),m=a+k-1,i;
		for(i=a;a+k>i;i++) if(b>=i) System.out.println(i);
		for(i=b-k+1;b>=i;i++) if(i>m&&i>=a) System.out.println(i);
	}
}

Measured memory_bytes: 21972
package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

var rdr = bufio.NewReaderSize(os.Stdin, 1000000)

func readLine() string {
    buf := make([]byte, 0, 1000000)
    for {
        l, p, e := rdr.ReadLine()
        if e != nil {
            panic(e)
        }
        buf = append(buf, l...)
        if !p {
            break
        }
    }
    return string(buf)
}

var sc = bufio.NewScanner(os.Stdin)

func nextLine() string {
    sc.Scan()
    return sc.Text()
}


func main(){
	set := make(map[int]struct{})
        set[1] = struct{}{}
	set[2] = struct{}{}
	set[3] = struct{}{}
	var A,B,res int
	A=nextInt()
	B=nextInt()
	delete(set,A)
	delete(set,B)

	for key, _ := range set {
		res=key
	}
	fmt.Println(res)

}

Measured memory_bytes: 640
#include<iostream>
#include<string>

using namespace std;

int main(){
    int N,r=0,b=0;
    string S;
    cin>>N>>S;

    for(int i=0;i<N;i++){
        if(S[i]=='R'){
            r++;
        }else{b++;}
    }
    if(r>b){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}

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

int main(void){
    int k;
    char s[111];
    scanf("%d%s",&k,s);
    if(strlen(s) <= k)puts(s);
    else {
        for(int i = 0;i < k;i++)printf("%c",s[i]);
        puts("...");
    }
}

Measured memory_bytes: 1660
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	int N,K;
	string S;
	vpint retu;
	scan(N>>K);
	scan(S);
	int ans=0;
	int flag=S[0]-'0',num=1;
	if(N<=2){
		prin(N);
		return 0;
	}
	rep1(i,N-1){
		if(S[i]=='1'){
			if(flag==0){
				flag=1;
				ans=max(ans,num);
				retu.push_back(mp(num,0));
				num=0;
			}
			num++;
		}
		else{
			if(flag==1){
				flag=0;
				retu.push_back(mp(num,1));
				num=0;
			}
			num++;
		}
		if(i==N-1){
			if(flag==1) retu.push_back(mp(num,1));
			else retu.push_back(mp(num,0));
		}
	}
	int bubunwa=0;
	int i;
	if(retu[0].second==1) i=0;
	else i=1;
	for(;i<=max(1,(int)retu.size()-2*K);i+=2){
		if(i<=1){
			rep(j,2*K+1){
				if(i+j>=(int)retu.size()) break;
				bubunwa+=retu[i+j].first;
			}

		}
		else{
			bubunwa-=(retu[i-2].first+retu[i-1].first);
			bubunwa+=(retu[i+2*K-1].first+retu[i+2*K].first);
		}
		ans=max(ans,bubunwa);
	}
	if(retu[0].second==0){
		int sum=0;
		rep(j,min((int)retu.size(),2*K)){
			sum+=retu[j].first;
		}
		ans=max(ans,sum);
	}
	if(retu.back().second==0){
		int sum=0;
		for(int j=(int)retu.size()-1;j>=max(0,(int)retu.size()-2*K);j--){
			sum+=retu[j].first;
		}
		ans=max(ans,sum);
	}
	prin(ans);
	return 0;
}


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

int main() {
	int n;
	long debt = 100000;
	
	cin >> n;
	for (int i = 0;i < n;i++) {
		debt = ceil(debt * 1.05 / 1000) * 1000;
	}
	cout << debt << endl;

	return 0;
}

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

int main(){
  int m,d,i,j,r=0;
  cin>>m>>d;
  for(i=2;i<=d/10;i++){
    for(j=2;j<10;j++){
      if(i*10+j>d) break;
      if(j*i<=m) r++;
    }
  }
  cout<<r<<endl;
  return 0;
}


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

int main(){
	int N;
	scanf("%d",&N);
	int A[N];
	int count = 0;
	int check = 0;
	for(int i=0; i<N; i++){
		scanf("%d",&A[i]);
	}

	while(check == 0){
		for(int i=0; i<N; i++){
			// printf("A[%d] = %d\n",i,A[i]);
			if(A[i] %2 == 0){
				A[i] /= 2;
			} 
			else{
				check = 1;
				break;
			}
		}
		count++;
	}
	printf("%d\n",count-1);

	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main{
    public static void main(String[] args) throws IOException{
        final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        final int n = Integer.parseInt(br.readLine());
        int ans = 0;
        for(int i = 0; i<n; i++){
            if(isPrime(Integer.parseInt(br.readLine()))) ans++;
        }
        System.out.println(ans);
    }
    private static boolean isPrime(int x){
        if(x<2) return false;
        if(x<=3) return true;
        if(x%2==0||x%3==0) return false;
        for(int i = 5; i*i<=x; i += 6){
            if(x%i==0||x%(i+2)==0) return false;
        }
        return true;
    }
}

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

int main()
{
    int n,a,b;
    cin>>n>>a>>b;
    int flag=0;
    for(int i=1;i<=n;i++)
    {
        int k=i,sum=0;
        while(k>0)
        {
            sum+=(k%10);
            k/=10;
        }
        if(sum>=a&&sum<=b)flag+=i;
    }
    cout<<flag<<endl;
}


Measured memory_bytes: 256
N = int(input().strip())
A = list(map(int, input().strip().split(' ')))
if N % 2 == 1:
  checklist = {0:1}
  for i in range((N-1)//2):
    checklist[(i+1)*2] = 2
else:
  checklist = {(i*2+1):2 for i in range(N//2)}

for a in A:
  if a in checklist and checklist[a] in {1,2}:
    checklist[a] -= 1
  else:
    print(0)
    exit()
print(int(2**(N//2))%1000000007)

Measured memory_bytes: 55276
// Author : Sarthak Kapoor
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define rep(i,n) for(int i=0;i<n;++i)
#define repa(i,a,n) for(int i=a;i<n;++i)
#define repr(i,n) for(int i=n-1;i>=0;--i)
#define repba(i,b,a) for(int i=b;i>=a;--i)
#define repab(i,a,b) for(int i=a;i<b;++i)
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define msi map<string,int>
#define mii map<int,int>
#define viip vector<pair<int,pair<int,int> > > 
#define mp make_pair
#define vip vector<pair<int,int> >
#define pb push_back 
#define po pop_back
#define fi first
#define sec second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define s(v) v.size()
ll mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());//use rng()%n for numbers in range [0,n-1]
ll gcd(ll a,ll b){
	if(b==0)return a;
	return gcd(b,a%b);
}
const int inf = 2e9;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
//	#ifndef ONLINE_JUDGE
 //   	freopen("input.txt", "r", stdin);
  //  	freopen("output.txt", "w", stdout);
//	#endif
	int n;
	cin>>n;
	int a[n][3];
	// vi a(n),b(n),c(n);
	rep(i,n){
		rep(j,3){
			cin>>a[i][j];
		}
		// cin>>a[i]>>b[i]>>c[i];
	}	
	int cost[n][3];
	rep(i,n){
		rep(j,3){
			cost[i][j]=0;
		}
	}
	rep(i,3){
		cost[0][i]=a[0][i];
	}
	repa(i,1,n){
		rep(j,3){
			rep(k,3){
				if(j == k)continue;
				cost[i][j] = max(cost[i][j],cost[i-1][k]+a[i][j]);
			}
		}
	}
	cout<<max(cost[n-1][0],max(cost[n-1][1],cost[n-1][2]));
	return 0;
}


Measured memory_bytes: 2560
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

const int N = 3010;
ll v[N][N], dp[N][N][4];

int main(void){
    int r, c, k;
    cin >> r >> c >> k;
    REP(i,k){
        int r = in() - 1, c = in() - 1, x = in();
        v[r][c] = x;
    }
    REP(i,r) REP(j,c) {
        FORR(k,3,0){
            if (k < 3) chmax(dp[i][j][k + 1], dp[i][j][k] + v[i][j]);
        }
        REP(k,4){
            if (i < r - 1) chmax(dp[i + 1][j][0], dp[i][j][k]);
            if (j < c - 1) chmax(dp[i][j + 1][k], dp[i][j][k]);
        }
    }

    ll ans = 0;
    REP(k,4) chmax(ans, dp[r - 1][c - 1][k]);
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 356352
import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N = int(input())
txy = [list(map(int,input().split())) for _ in range(N)]
t = 0
x = 0
y = 0
j = 0
for i in range(N):
    a = abs(txy[i][1]-x) + abs(txy[i][2]-y)
    b = txy[i][0]-t
    x = txy[i][1]
    y = txy[i][2]
    t = txy[i][0]
    if b >= a and (b-a) % 2 == 0:
        continue
    else:
        j = 1
        break
if j == 0:
    print("Yes")
else:
    print("No")







Measured memory_bytes: 27340
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
#define MV 200
#define INF 1e10

struct edge{int to,cost; };
vector <edge> G[MV];

int V,E;
long long d[MV+1];//???????????????????´?

bool bellmanford(int s){
  fill(d,d+MV,INF);
  d[s] = 0;
  int c = 0;
  bool upd = false;
  while(true){
    upd = false;
    for(int i = 0;i < V;i++){
      for(int j = 0;j < G[i].size();j++){
	edge e = G[i][j];
	if(d[i] != INF && d[e.to] > d[i] + e.cost){
	  d[e.to] = d[i] + e.cost;
	  upd = true;
	}
      }
    }
    if(!upd)
      break;
    if(c == V-1)
      return true;//?????????????????????
    c++;
  }
  return false;
}

int main(){
  d[MV] = INF+10;
  int first;
  bool flag;
  cin >> V >> E;
  for(int i = 0;i < E;i++){
    int f,t;
    edge e;
    cin >> f >> e.to >> e.cost;
    G[f].push_back(e);
    /*
      G[f]??????f????????§????????????????´???????????????????
     */
    t = e.to;
    /*
    e.to = f;
    G[t].push_back(e);
    */
  }
  long long vec[V][V];
  
  for(int i = 0;i<V;i++){
    flag = bellmanford(i);
    for(int j = 0;j < V;j++){
      vec[i][j] = d[j];
    }
    if(flag == true)
      break;
  }
  if(flag == true)
    cout << "NEGATIVE CYCLE" << endl;
  else{
    for(int i = 0;i < V;i++){
      for(int j = 0;j < V;j++){
	if(vec[i][j] == INF){
	  if(j != V-1)
	    cout << "INF" << " ";
	  else
	    cout << "INF";
	}
	else{
	  if(j != V-1)
	    cout << vec[i][j] << " ";
	  else
	    cout << vec[i][j];
	}
      }
      cout << endl;
    }
    //cout << endl;
  }
  
}

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

main()
{
	int q,s,h,n;
	long long d;
	scanf("%d %d %d %lld",&q,&s,&h,&d);
	scanf("%d",&n);
	q=q*4;
	s=s*2;
	long long one=min(q,min(s,h)),two;
	two=min(one*2,d);
	long long ans=0;
	ans+=(n/2)*two;
	if(n%2==1)
	{
		ans+=one;
	}
	printf("%lld",ans);
}

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

def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)

ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            ans+=gcd(gcd(i,j),l)
print(ans)

Measured memory_bytes: 76940
#include <iostream>
#include<cstdio>
#include<stdlib.h>
#include<string>

int top, S[1000];

void push(int x){
    top++;
    S[top] = x;
}

int pop(){
    top--;
    return S[top+1];
}
using namespace std;
int main(void){
    int x, y;
    int top = 0;
    char s[100];
    while(scanf("%s", s) != EOF){
        if(s[0] == '+'){
            x = pop();
            y = pop();
            push(x+y);
        }
        else if(s[0] == '-'){
            x = pop();
            y = pop();
            push(y-x);
        }
        else if(s[0] == '*'){
            x = pop();
            y = pop();
            push(x*y);
        }
        else{
            x = atoi(s);
            push(x);
        }
    }
    cout<<pop()<<endl;
    return 0;
}



Measured memory_bytes: 3220
#include <iostream>
#include <string>
#include <stack>

using namespace std;

int main(){
	int n, count;
	count = 0;
	while (cin >> n){
		for (int i = 0; i < 10; i++){
			for (int j = 0; j < 10; j++){
				for (int k = 0; k < 10; k++){
					for (int l = 0; l < 10; l++){
						if (i + j + k + l == n){
							count++;
						}
					}
				}
			}
		}
		cout << count << endl;
		count = 0;
	}
	return 0;
}


Measured memory_bytes: 3100
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

#define rep(i,n) for(int i=0; i<(n); i++)
#define repc(i,s,e) for(int i=(s); i<(e); i++)
#define pb(n) push_back((n))
#define mp(n,m) make_pair((n),(m))
#define all(r) r.begin(),r.end()
#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;






int main() {
	vi v(100100, 1);
	v[0] = 0;
	v[1] = 1;
	for (int i = 2; i < 100100; i++) {
		if (v[i] == 1) {
			for (int j = 2; j <= 100100 / i; j++) {
				v[i*j] = 0;
			}
		}
	}
	int n;
	while (cin >> n&&n > 0) {
		int ans = 5;
		for (int i = n; i > 1; i--) {
			if (v[i] && v[i - 2]) {
				ans = i;
				break;
			}
		}
		cout << ans - 2 << " " << ans << endl;
	}
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define umap unordered_map
#define all(v) v.begin(),v.end()
#define st first
#define nd second
#define L (no<<1)
#define R L|1
#define mid (s + e) / 2
#define ln '\n'
#define MAX (1<<31)
#define MOD 1000000007
#define N 300005
using namespace std;
typedef long long ll;
typedef pair<ll ,ll> pii;
typedef vector<int> vi;
string s;
bool isP(string s2){
    //cerr << s2.substr(0, s2.size() / 2) << " " << s2.substr(s2.size() / 2) << ln;
    string s3, s4;
    if(s2.size() % 2){
        s3 = s2.substr(0, s2.size() / 2);
        reverse(all(s3));
        return s3 == s2.substr(s2.size() / 2 + 1, s2.size() / 2);
    }
    else {
        s4 = s2.substr(0, s2.size() / 2);
        reverse(all(s4));
        return s4 == s2.substr(s2.size() / 2);
    }
}
int main(){
    //#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    //#endif
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);cout.tie(NULL);
    cin >> s;
    cerr << s.substr(0, (s.size() - 1)/ 2) << " " << s.substr((s.size() + 3) / 2 - 1);
    string s2 = s.substr(0, (s.size() - 1)/ 2), s3 = s.substr((s.size() + 3) / 2 - 1);
    if(!isP(s) || !isP(s2) || !isP(s3)){
        cout << "No";
    }
    else cout << "Yes";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> h(n), dp(n,0);
    rep(i, n)cin >> h.at(i);
    dp[0] = 0;
    REP(i, n-1){
        int mi = 1000000000;
        for(int j = max(0,i-k); j < i; j++){
            mi = min(mi, abs(h.at(i)-h.at(j))+dp[j]);
        }
        dp[i] = mi;
    }
    cout << dp[n-1];
}



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



typedef long long ll;
ll gcd(ll a, ll b) { return a ? gcd(b%a, a) : b; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
int N, M;
int A[1010];
//-----------------------------------------------------------------------------------
int main() {
	cin >> N >> M;
	rep(i, 0, N) cin >> A[i];

	int loop = lcm(N, M) / M;
	ll ans = 0;
	rep(i, 0, loop) {
		int mi = 1010, ma = -1;
		rep(j, 0, M) {
			int ii = (i * M + j) % N;
			mi = min(mi, A[ii]);
			ma = max(ma, A[ii]);
		}
		ans += ma - mi;
	}
	cout << ans << endl;
}

Measured memory_bytes: 3032