akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<stack>
#include<queue>
#include<list>
#include<set>
#include<cmath>

#define REP(i,n) for(int (i) = 0;(i) < (n);(i)++)
using namespace std;

class node{
public:
	int id;
	int parent,child1,child2,sibling;
	int degree,depth,height;
	node():id(-1),parent(-1),child1(-1),child2(-1),sibling(-1),degree(0),depth(0),height(0){};
	
	friend ostream& operator<<(ostream& os,const node& N){
		cout << "node " 		<< N.id ;
		cout << ": parent = "	<< N.parent;
		cout << ", sibling = " 	<< N.sibling;
		cout << ", degree = " 	<< N.degree;
		cout << ", depth = " 	<< N.depth;
		cout << ", height = "	<< N.height;
		cout << ", ";
		if(N.parent==-1) cout << "root";
		else if(N.child1==-1 && N.child2==-1) cout << "leaf";
		else cout << "internal node";
		cout << endl;
	}
};

int main(){
	int n,m;
	cin >> n;
	vector<node> N(n);
	REP(i,n){
		N[i].id=i;
	}
	REP(i,n){
		int id,c1,c2;
		cin >> id >> c1 >> c2;
		N[id].child1 = c1;
		N[id].child2 = c2;
		N[id].degree = ((c1!=-1)?1:0)+((c2!=-1)?1:0);
		if(c1 != -1) N[c1].sibling = c2,N[c1].parent = id;
		if(c2 != -1) N[c2].sibling = c1,N[c2].parent = id;
	}
	int i=0;
	while(N[i].parent!=-1)i++;
	queue<node> que;
	que.push(N[i]);
	while(!que.empty()){
		node n = que.front();que.pop();
		int c1=n.child1,c2=n.child2;
		if(c1 != -1) {
			N[c1].depth = n.depth+1;
			que.push(N[c1]);
		}
		if(c2 != -1) {
			N[c2].depth = n.depth+1;
			que.push(N[c2]);
		}
	}
	for(int d=n;d>=0;d--){
		REP(j,n){
			if(N[j].depth == d){
				int c1=N[j].child1,c2=N[j].child2;
				if(c1 != -1) N[j].height = max(N[j].height,N[c1].height+1);
				if(c2 != -1) N[j].height = max(N[j].height,N[c2].height+1);
			}
		}	
	}
	REP(j,n) cout << N[j];
	return 0;
}

Measured memory_bytes: 3048
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll num[200000];
ll s[200000];
bool fl[200000];
int fc = 0;
ll fn=0,sn=0;
int main(){
    ll n;
    cin>>n;
    for(ll i=0;i<n;i++)
    {
        cin>>num[i];
        if(num[i]>fn)
        {
            sn = fn;
            fn = num[i];
            fl[i] = true;
            fc=1;
        }
        else if(num[i] == fn)fc++;
        else if(num[i]>sn && fn != num[i])
        {
            sn = num[i];
        }
    }
    //cout<<fn<<","<<fc<<endl;
    for(ll i=0;i<n;i++)
    {
        if(num[i] != fn)
        {
            cout<<fn<<endl;
        }
        else if(sn==0){
            cout<<fn<<endl;
        }

        else if(fc >1)cout<<fn<<endl;
        else cout<<sn<<endl;
    }
}

Measured memory_bytes: 3200
n,m = map(int,input().split())
h = list(map(int,input().split()))
d = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    d[a].append(b)
    d[b].append(a)

cnt = 0
for i in range(n):
    H = h[i]
    max1 = 0
    for j in d[i]:
        max1 = max(max1,h[j])
    if H > max1:
        cnt +=1        
print(cnt)

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

using namespace std;

int main() {
	int n;
	int a;
	int count = 0;
	cin >> n;
	
	for(int i = 0; i < n; i++){
		cin >> a;
		if(a % 2 == 1){
			count++;
		}
	}

	if(count % 2 == 1){
		cout << "NO" << endl;
	}else{
		cout << "YES" << endl;
	}

	return 0;
}
/*


*/


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main() {
    int n;  cin >> n;
    map<int,int> mp;
    for (int i = 0; i < n; i++){
        int a;  cin >> a;
        mp[a]++;
    }
    int ans = 0, even = 0;
    for (auto m: mp) {
        if (m.second % 2) {
            m.second = 1;
            ans++;
        }
        else {
            m.second = 2;
            even++;
        }
    }

    if (even % 2)
        ans += even-1;
    else 
        ans += even;

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

Measured memory_bytes: 8204
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int32_t main(){
	int n;cin>>n;
	set<int> s;
	while(n--){
		int tmp;cin>>tmp;
		if(s.count(tmp)){
			s.erase(tmp);
		}
		else {
			s.insert(tmp);
		}
	}
	cout<<s.size();
}


Measured memory_bytes: 4864
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0; (i)<(n); (i)++)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define ll long long
#define pii pair<int,int> 
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
int inf=1000001000;
ll INF=100000000000000000;
//int 2×10の9乗
//vector<vector<int>> a(n, vector<int>(m));
//rep(i,n) rep(j,m) cin >> a[i][j]; 
//cout << fixed << setprecision(10);
//int gcd(int x, int y){
//if(y==0) return x;
//return gcd(y, x%y);
//}
//sort小さい順(昇順)
//g++ code.cpp   ./a.out 
int main(){
  ll n; 
  cin >> n;
  ll ans = INF;
  for(ll i=1; i*i<=n; i++){
   if(n%i != 0) continue;
   ll j = n/i;
   ans = min(ans, i+j-2); 
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <list>

using namespace std;

void print_list(list<int> &V)
{
	for(list<int>::iterator it = V.begin();
		it != V.end();it ++)
	{
		if(it ==  V.begin()){
			cout << *it;
		}
		else{
			cout << " " << *it;
		}
	}
	cout << endl;
}
void delete_num(list<int> &V, int x)
{
	for(list<int>::iterator it = V.begin();
		it != V.end();it ++)
	{	
		if(*it == x){
			V.erase(it);
			break;
		}
	}
}
int main(void)
{	
	ios_base::sync_with_stdio(false);

	list<int> V;
	
	int n;
	cin >> n;

	for(int i = 0; i < n; i++){
		string s;
		cin >> s;
		
		if(s == "insert"){
			int x;
			cin >> x;
			//V.(V.begin(), x);
			V.push_front(x);
		}
		else if(s == "delete"){
			int x;
			cin >> x;
			delete_num(V, x);
		}
		else if(s == "deleteFirst"){
			V.pop_front();
		}
		else{
			V.pop_back();
		}
	}
	print_list(V);
	
	return 0;
}

Measured memory_bytes: 34504
#include <bits/stdc++.h>
#define LL __int128
#define ll long long
#define sc(a) scanf("%d", &a)
#define sc2(a, b) scanf("%d%d", &a, &b)
#define sc3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define scl(a) scanf("%lld", &a)
#define scl2(a, b) scanf("%lld%lld", &a, &b)
#define ss(a) scanf("%s", a)
#define mem(a, b) memset(a, b, sizeof(a))
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define PII pair<int, int>
using namespace std;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
struct node{
	ll x, y;
}a[200005];
bool cmp1(node a, node b){
	return abs(a.x) + abs(a.y) < abs(b.x) + abs(b.y);
}
int main(){
	int n; 
	cin >> n;
	for(int i = 1; i <= n; i ++){
		cin >> a[i].x >> a[i].y;
	}
	sort(a + 1, a + n + 1, cmp1);
	ll ans = a[n].x + a[n].y - a[1].x - a[1].y;
    for(int i = 1; i <= n; i ++){
        a[i].x -= 2e9;
    }
    sort(a + 1, a + n + 1, cmp1);
    ll res = abs(a[n].x - a[1].x) + abs(a[n].y - a[1].y);
    cout << max(res, ans) << endl;
	return 0;
}

Measured memory_bytes: 6724
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

int main(int argc,char** argv){
  int n;
  cin >> n;
  int a[n],b[n],c[n];
  for(int i = 0; i < n; i++){
    cin >> a[i] >> b[i] >> c[i];
  }
  int h[n][3];
  h[0][0] = a[0];
  h[0][1] = b[0];
  h[0][2] = c[0];

  for(int i = 1; i < n; i++){
    h[i][0] = max(h[i-1][1],h[i-1][2])+a[i];
    h[i][1] = max(h[i-1][0],h[i-1][2])+b[i];
    h[i][2] = max(h[i-1][0],h[i-1][1])+c[i];
  }
  cout << max({h[n-1][0],h[n-1][1],h[n-1][2]}) << endl;
  return 0;
}


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

using namespace std;

void solve()
{
	stack<int> numStack;
	string str;
	getline(cin, str);
	for (int i = 0; i < str.size(); ++i)
	{
		if (str[i] == '+')
		{
			int a = numStack.top();
			numStack.pop();
			int b = numStack.top();
			numStack.pop();
			numStack.push(b + a);
		}
		else if (str[i] == '-')
		{
			int a = numStack.top();
			numStack.pop();
			int b = numStack.top();
			numStack.pop();
			numStack.push(b - a);
		}
		else if (str[i] == '*')
		{
			int a = numStack.top();
			numStack.pop();
			int b = numStack.top();
			numStack.pop();
			numStack.push(b * a);
		}
		else if (str[i] != ' ')
		{
			int temp = str[i] - '0';
			while (str[++i] != ' ')
			{
				temp = temp * 10 + str[i] - '0';
			}
			numStack.push(temp);
		}
	}
	cout << numStack.top() << endl;
}

int main()
{
	solve();
	return(0);
}

Measured memory_bytes: 1184
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

void solve() {
	string a; cin >> a;
	string b;
	for(char c : a) if(c != 'x') b.pb(c);
	string c = b; reverse(all(c));
	if(b != c) {
		puts("-1");
		return;
	}
	if(sz(b) == 0) { puts("0"); return; }
	int la = (sz(b) + 1) / 2;
	int n = sz(a);
	int f = -1;
	for(int i=0, j=0;i<n;i++) {
		if(j < sz(b) && b[j] == a[i]) ++j;
		if(j == la) {
			f = i; break;
		}
	}
	int g = -1;
	for(int i=n-1, j=0;i>=0;i--) {
		if(j < sz(b) && b[sz(b)-1-j] == a[i]) ++j;
		if(j == la) {
			g = i; break;
		}
	}
	int ans = 0;
	while(f >= 0 || g <= n-1) {
		char ca = (f >= 0 ? a[f] : -1);
		char cb = (g <= n-1 ? a[g] : -1);
		if(ca == cb) --f, ++g;
		else {
			if(ca == 'x') --f, ans++;
			else ++g, ++ans;
		}
	}
	printf("%d\n", ans);
}

int main(){
	int Tc = 1; // scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		// printf("Case #%d: ", tc);
		solve();
	}
	return 0;
}

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

using namespace std;

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

int main(){
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  REP(i, n) cin >> a[i];
  vector<bool> r(n, true);
  REP(i, m){
    int x, y;
    cin >> x >> y;
    --x, --y;
    if(a[x] <= a[y]) r[x] = false;
    if(a[y] <= a[x]) r[y] = false;
  }
  int res = 0;
  REP(i, n) if(r[i]) ++res;
  cout << res << endl;
  return 0;
}

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

int main()
{
  int n, d;
  cin >> n >> d;
  vector<vector<int>> x(n, vector<int>(d));
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < d; j++)
    {
      cin >> x[i][j];
    }
  }
  int ans = 0;
  for (int i = 0; i < n - 1; i++)
  {
    for (int j = i + 1; j < n; j++)
    {
      double buf = 0;
      for (int k = 0; k < d; k++)
      {
        int tmp = abs(x[i][k] - x[j][k]);
        buf += pow(tmp, 2);
      }
      buf = sqrt(buf);
      if (float(buf) == buf)
      {
        ans++;
      }
    }
  }

  cout << ans << endl;
}


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

int main(){
  int H, W;
  string S[50];
  cin >> H >> W;
  for(int i=0; i<H; i++){
    cin >> S[i];
  }
  for(int i=0; i<H; i++){
    for(int j=0; j<W; j++){
      int count=0;
      if(S[i][j]=='.'){
        if(j-1>=0){
          if(i-1>=0 && S[i-1][j-1]=='#') count++;
          if(i+1<H && S[i+1][j-1]=='#') count++;
          if(S[i][j-1]=='#') count++;
        }
        if(j+1<W){
          if(i-1>=0 && S[i-1][j+1]=='#') count++;
          if(i+1<H && S[i+1][j+1]=='#') count++;
          if(S[i][j+1]=='#') count++;
        }
        if(i-1>=0 && S[i-1][j]=='#') count++;
        if(i+1<H && S[i+1][j]=='#') count++;
        S[i][j]=(char)(count+'0');
      }
    }
  }
  for(int i=0; i<H; i++){
    cout << S[i] << endl;
  }
  return 0;
}

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

int main()
{
    int H, N;
    cin >> H >> N;
    int sum = 0;    
    int i;
    int a;
    for(i=0;i<N;i++){
        cin >> a;
        sum += a;
    }
    if(sum >= H){
        cout << "Yes";
    }else{
        cout << "No";
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>
#include <string>
#include <set>
using namespace std;

int main()
{
	int32_t N;
	cin >> N;

	vector<int32_t> dp(N + 1, numeric_limits<int32_t>::max());
	dp[0] = 0;
	for (int32_t i = 0; i < N; i++) {
		dp[i + 1] = min(dp[i + 1], dp[i] + 1);
		for (int32_t six_power = 6; i + six_power <= N; six_power *= 6) {
			dp[i + six_power] = min(dp[i + six_power], dp[i] + 1);
		}
		for (int32_t nine_power = 9; i + nine_power <= N; nine_power *= 9) {
			dp[i + nine_power] = min(dp[i + nine_power], dp[i] + 1);
		}
	}

	cout << dp[N] << endl;

	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

int mem;

template<class T> void chmax(T &a,T b,int c){
  if (a<b){
    a=b;
    mem = c;
  }
}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}



int main(){
  int n;
  cin >> n;
  int ans = 0;

  rep(i,n){
    int tmp;
    cin >> tmp;
    tmp--;
    ans += tmp;
  }
  
  cout << ans;

  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using vpii = vector<pair<int, int>>;
using vpll = vector<pair<ll, ll>>;
// ceil() 切り上げ, floor() 切り捨て
// next_permutation(all(x))

int		main(void)
{
	string S;
	cin >> S;

	int size = (int)S.size() / 2 - 1;
	while (1)
	{
		string A = S.substr(0, size);
		string B = S.substr(size, size);
		if (A == B)
		{
			cout << size * 2 << endl;
			return 0;
		}
		size--;
	}
}



Measured memory_bytes: 256
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
import sys
sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e30)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N = i_inpl()
    H = l_inpl()
    ans = 0
    tmp = 0
    for i in range(N-1):
        if H[i] >= H[i+1]:
            tmp += 1
        else:
            ans = max(ans, tmp)
            tmp = 0
    ans = max(ans, tmp)
    print(ans)
if __name__ == "__main__":
    main()


Measured memory_bytes: 63760
#include <bits/stdc++.h>
#include <string>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <numeric>
using namespace std;


int main(){
  long long A;
  cin >> A;
  if(A%2 == 1){
    cout << A*2 << endl;
  }
  else{
    cout << A << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define EPS (1e-9)
#define INF (1e17)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
//long long INF=(long long)1E17;
#define i_7 (long long)(1e9+7)
//#define i_7 998'244'353
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
long long po(long a, long b){
    if(b==0){
        return 1;
    }
    
    long long z = po(a,b/2);
    z = mod(z*z);
    if(b%2!=0){
        z = mod(a*z);
    }
    return z;
}

bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=std::sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}

long long gcd_(long long a, long long b){
  if(a<b){
    std::swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}

//using namespace std;
//using namespace boost::multiprecision;
//using namespace __gnu_pbds;

int main(){
  using namespace std;
  int a, b;
  cin>>a>>b;
  if(a > b){
    swap(a, b);
  }
  REP(i,b){
    cout<<a;
  }
  cout<<endl;
  return 0;
}


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

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

const int MAXN = 21;
const ll MOD = 1e9+7;

int n, adj[MAXN+10][MAXN+10];
ll dp[(1<<MAXN)+10];

ll solve(int bitmask)
{
    if(bitmask==(1<<n)-1) return 1;
    ll &ret=dp[bitmask];
    if(ret!=-1) return ret;

    int now=__builtin_popcount(bitmask);

    ret=0;
    int i;
    for(i=0; i<n; i++)
    {
        if(adj[now][i] && (bitmask&(1<<i))==0) ret=(ret+solve(bitmask|(1<<i)))%MOD;
    }
    return ret;
}

int main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int i, j;

    memset(dp, -1, sizeof(dp));

    scanf("%d", &n);
    for(i=0; i<n; i++) for(j=0; j<n; j++) scanf("%d", &adj[i][j]);

    printf("%lld", solve(0));

    return 0;
}


Measured memory_bytes: 16640
N,Y = map(int,input().split())
answer = (-1,-1,-1)
for x in range(N + 1):
    for y in range(N + 1 - x):
        z = N - x - y
        if 0 <= z <= N and 10000 * x + 5000 * y + 1000 * z == Y:
            answer = x, y, z
            break
    else:
        continue
    break
print(*answer)

Measured memory_bytes: 41068
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n,m;
vector<int>edge[200005];
string str;
int cnt[200005][2];
bool used[200005];
int main(){
	scanf("%d%d",&n,&m);
	cin>>str;
	for(int i=0;i<m;i++){
		int a,b; scanf("%d%d",&a,&b);
		edge[a].pb(b);
		if(a != b) edge[b].pb(a);
	}
	queue<int>que;
	for(int i=1;i<=n;i++){
		for(int j=0;j<edge[i].size();j++){
			int hoge = str[edge[i][j]-1]-'A';
			cnt[i][hoge]++;
		}
		if(cnt[i][0] == 0 || cnt[i][1] == 0){
			que.push(i);
		}
	}
	while(!que.empty()){
		int q = que.front(); que.pop();
		if(used[q]) continue;
		used[q] = 1;
		int hoge = str[q-1]-'A';
		for(int i=0;i<edge[q].size();i++){
			cnt[edge[q][i]][hoge]--;
			if(cnt[edge[q][i]][hoge] == 0 && !used[edge[q][i]]){
				que.push(edge[q][i]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(!used[i]){
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;
}

Measured memory_bytes: 12548
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=3e5+5;
int a[N];
int b[N],bn;
int n;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    bn=unique(b+1,b+n+1)-b;
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+bn+1,a[i])-b;
    int ans=0;
    for(int i=1;i<=n;i++){
        if(i%2!=a[i]%2)
            ans++;
    }
    ans/=2;
    printf("%d\n",ans);
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define mod 1000000007
#define autoit(x,it) for(auto it = x.begin(); it != x.end(); it++)
#define rep(n) for(ll i = 0; i < n; i++)

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 

#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 

using namespace std;


int main()
{
   FAST/**/
   
   ll n;
   cin>>n;
   
   string s,t;
   cin>>s>>t;
   
   rep(2*n)
        if(i%2 == 0)
            cout<<s[i/2];
        else cout<<t[i/2];    
   
   return 0;        
}  
   

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

int main(){
  long N,H;
  cin >> N >> H;
  long a[N],b[N];
  for(int i=0;i<N;++i){
    cin >> a[i] >> b[i];
  }
  sort(a,a+N,greater<int>());
  sort(b,b+N,greater<int>());
  long sum=0,cnt=0;
  int i=0;
  while(sum<H){
    if(a[0]<b[i]){
      sum+=b[i];
      ++i;
      ++cnt;
    }
    else if(i==N-1){
      cnt+=(int)ceil((double)(H-sum)/a[0]);
      break;
    }
    else{
      sum+=a[0];
      ++cnt;
    }
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>

using namespace std;

int main(int argc, char const* argv[])
{
    int A, B;
    scanf("%d%d", &A, &B);
    if ( A > B ) printf("%d\n", A * 2 - 1);
    else if ( A == B ) printf("%d\n", A * 2);
    else printf("%d\n", B * 2 - 1);

    return 0;
}

Measured memory_bytes: 256
import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
s = S()
w = I()
ans = s[::w]
print(ans)


Measured memory_bytes: 74512
#!/usr/bin/env python3
import sys

def solve(a: str, b: str, c: str):
    permutation = [(0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,1,0),(2,0,1)]
    abc = (a,b,c)
    ans = 10**4

    for i_1,j_1,k_1 in permutation:
        A = abc[i_1]
        B = abc[j_1]
        C = abc[k_1]
        LENA = len(A)
        LENB = len(B)
        LENC = len(C)

        AB = [False]*(LENA+1)
        BC = [False]*LENB+[True]*2010
        AC = [False]*(LENA)+[True]*(2010)
        AB[LENA] = True

        # 前計算
        for i in range(LENA): # Aのindex
            for j in range(i,min(LENA,LENB+i)):
                if A[j] != B[j-i] and A[j] != "?" and B[j-i] != "?":
                    break
            else:
                AB[i] = True

        for i in range(LENB): # Bのindex
            for j in range(i,min(LENB,LENC+i)):
                if B[j] != C[j-i] and B[j] != "?" and C[j-i] != "?":
                    break
            else:
                BC[i] = True

        for i in range(LENA): # Aのindex
            for j in range(i,min(LENA,LENC+i)):
                if A[j] != C[j-i] and A[j] != "?" and C[j-i] != "?":
                    break
            else:
                AC[i] = True        

        # x: AとBがどれだけずれてるか
        # y: BとCがどれだけずれてるか
        length = 10**4
        for x in range(LENA+1):
            for y in range(2001+1):
                if AB[x] and BC[y] and AC[x+y]:
                    length = min(length,max(LENA,x+LENB,x+y+LENC))
        ans = min(ans,length)
 
    print(ans)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    a = next(tokens)  # type: str
    b = next(tokens)  # type: str
    c = next(tokens)  # type: str
    solve(a, b, c)

if __name__ == '__main__':
    main()


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

#ifdef LOCAL
#define debug(var) cerr << (#var) << " = " << (var) << endl;
#else
#define debug(var)
#endif

void init() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}

const int N = 1e5+23;

int a[N];

void solve() {
  int n; scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", a+i);
  }
  sort(a, a+n);
  if (a[n-1]-1 > a[0]) {
    puts("No");
    return;
  }
  int lo = 0;
  for (int i = 0; i < n; ++i) {
    if (a[i] == a[0]) ++lo;
    else break;
  }
  int hi = n-lo;
  int x = a[0]-lo+1;
  if (hi) {
    if (1 <= x && x <= hi/2) puts("Yes");
    else puts("No");
  } else {
    if (x == 0 || n/2 >= a[0]) puts("Yes");
    else puts("No");
  }
}

int main() {
  init();
  int t = 1; //scanf("%d", &t);
  while (t--) {
    solve();
  }
  return 0;
}


Measured memory_bytes: 4180
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9;

int main(){
    int n; cin>>n;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int sum=0,r=0;
    ll ans=0;
    for(int l=0;l<n;l++){
        while(r<n&&(sum^a[r])==sum+a[r]){
            sum+=a[r++];
        }
        ans+=r-l;
        sum-=a[l];
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define bg begin()
#define en end()


using namespace std;

typedef long long ll;

static const long long MOD = 1000000007;

int ans;
int N;
map<int, bool> m;


int main(void) {
    scanf("%d", &N);
    rep(i, 0, N) {
        int a;
        cin >> a;
        if (m[a]) {
            puts("NO");
            return 0;
        } else {
            m[a] = true;
        }

    }
   

  
    puts("YES");

	return 0;
}


Measured memory_bytes: 9600
#include<cstdio>
#include<algorithm>

using namespace std;

#define INF 1 << 29

int dp[41][401][401];

int main(){
	int n, ma, mb; scanf("%d %d %d", &n, &ma, &mb);
	int a[40], b[40], c[40];
	for(int i = 0; i < n; i++) scanf("%d %d %d", &a[i], &b[i] ,&c[i]);
	for(int i = 0; i < 41; i++) for(int j = 0; j < 401; j++) fill(dp[i][j], dp[i][j] + 401, INF);
	dp[0][0][0] = 0;
	for(int i = 0; i < n; i++) for(int j = 0; j < 401; j++) for(int k = 0; k < 401; k++){
		dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k]);
		if(j - a[i] >= 0 && k - b[i] >= 0) dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j - a[i]][k - b[i]] + c[i]);
	}
	int res = INF;
	for(int i = 1; i < 401; i++){
		if(i * ma > 400 || i * mb > 400) break;
		res = min(res, dp[n][i * ma][i * mb]);
	}
	printf("%d\n", res == INF ? -1 : res);
	return 0;
}

Measured memory_bytes: 25856
#pragma region
#include <bits/stdc++.h>
using namespace std;
inline void ci(void){
  return;
}
template <typename First, typename... Rest>
void ci(First& first, Rest&... rest){
  cin >> first;
  ci(rest...);
  return;
}
inline void co(void){
  cout << "\n";
  return;
}
template <typename First, typename... Rest>
void co(First first, Rest... rest){
  cout << first << " ";
  co(rest...);
  return;
}
#define ll long long
#define ld long double
#define st string
#define dl double
#define wh while
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define tp tuple
#define ft first
#define sc second
#define ve vector
#define tos to_string
#define len length
#define rt return 0
#define br break
#define con continue
#define lcm(n, m) (n * m / gcd(n, m))
#define np next_permutation
#define repi(i, m, n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i, n) repi(i, 0, n)
#define repill(i, m, n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define repll(i, n) repill(i, 0, n)
#define revi(i, m, n) for(int i=(int)(m);i>(int)(n);i--)
#define rev(i, n) revi(i, 0, n)
#define revill(i, m, n) for(ll i=(ll)(m);i>(ll)(n);i--)
#define revll(i, n) revill(i, 0, n)
#define sz(v) ((int)(v).size()) 
#define each(i, n) for(auto&& i: n)
#define all(n) (n.begin(), n.end())
#define allr(n) (n.rbegin(), n.rend())
#define sp(n) cout << fixed << setprecision(n)
#pragma endregion
// sqrt ルート, int 2*10^9, gcd　最大公約数
// __builtin_popcount bitの個数

int main() {
  int a, b;
  ci(a, b);
  if((a + b) % 2 == 0){
    co((a + b) / 2);
  }
  else{
    co((a + b) / 2 + 1);
  }
}


Measured memory_bytes: 256
import java.io.{BufferedOutputStream, BufferedReader, InputStreamReader, PrintWriter}

object Main {
  def main(args: Array[String]): Unit = {
    val in = new BufferedReader(new InputStreamReader(System.in))
    val out = new PrintWriter(new BufferedOutputStream(System.out))
    val n = in.readLine().toInt

    if (n % 2 == 0) {
      out.println((n * n - 2 * n) / 2)
      for (i <- 1 until n) {
        for (j <- (i + 1) to n) {
          if (n + 1 - j != i) {
            out.println(s"${i} ${j}")
          }
        }
      }
    } else {
      out.println((n * n - 2 * n + 1) / 2)
      for (i <- 1 until n) {
        for (j <- (i + 1) to n) {
          if (n - j != i) {
            out.println(s"${i} ${j}")
          }
        }
      }
    }

    out.flush()
  }
}


Measured memory_bytes: 28080
#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 RREP(i, n) for(int (i)=((int)(n)-1); (i)>=0; i--)
#define RFOR(i, a, b) for(int (i) =((int)(b)-1); (i)>=(int)a; i--)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define F first
#define S second

using namespace std ;
typedef long long ll;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef pair<int, int> pint;
const int Inf = 1e9;
const double EPS = 1e-9;



int main()
{
  string a, b ;
  cin >> a >> b ;
  int n = a.size() ;
  int m = b.size() ;
  
  if(n>m){
    cout <<"GREATER"<<endl ;
  }
  else if(n<m){
    cout <<"LESS"<<endl ;
  }
  else{
    REP(i,n){
      if(a.at(i)>b.at(i)){
        cout <<"GREATER"<<endl ;
        return 0 ;
      }
      else if(a.at(i)<b.at(i)){
        cout <<"LESS"<<endl ;
        return 0 ;
      }
      if(i==n-1){
        cout <<"EQUAL"<<endl ;
      }
    }
  }
        
  
  
  return 0 ;
}



Measured memory_bytes: 256
#include <stdio.h>
#include <ctype.h>
int a,b,i;
int main(){
 scanf("%d %d",&a,&b);
 char s[a] ;
 for(i=0;i<=a;i++)
  scanf("%c",&s[i]);
for(i=0;i<=a;i++)
  if(i==b){
    s[i]=tolower(s[i]);
  }
for(i=0;i<=a;i++)
  printf("%c",s[i]);
  
  return 0;
}

Measured memory_bytes: 1612
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<deque>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#include<iomanip>
#include<cassert>
#include<regex>
#include<bitset>
#include<complex>
#include<chrono>
#include<random>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define rrep(i,a) for(int i=(int)a-1;i>=0;--i)
#define REP(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RREP(i,a,b) for(int i=(int)a-1;i>=b;--i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
typedef std::vector<int> vi;
typedef std::vector<std::vector<int>> vvi;
typedef std::vector<long long> vl;
typedef std::vector<std::vector<long long>> vvl;
#define out(x) cout<<x<<"\n";
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;

ll gcd(ll n, ll m) {
    ll tmp;
    while (m!=0) {
        tmp = n % m;
        n = m;
        m = tmp;
    }
    return n;
}

ll lcm(ll n, ll m) {
    return abs(n) / gcd(n, m)*abs(m);//gl=xy
}
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
 
using namespace std;

const ll INFTY=(numeric_limits<ll>::max())/2;
vector<vector<ll>>d;//d[u][v]は辺uvのコスト、ただし存在しないときINFTY,d[i][i]=0,d.resize(V,vector<int>(V,INFTY));とすること

void warshall_floyd(int V){//Vは頂点数
	for(int k=0;k<V;++k){//経由する頂点
		for(int i=0;i<V;++i){//始点となる頂点
			for(int j=0;j<V;++j)//目的地の頂点
      d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
		}
	}
}

void solve(){
    int n;
    cin>>n;
    d.resize(n,vector<ll>(n,INFTY));
    vector<vector<ll>>a(n,vector<ll>(n));
    rep(i,n){
        rep(j,n){
            cin>>a[i][j];
            d[i][j]=a[i][j];
        }
    }
    warshall_floyd(n);
    set<pair<int,int>>ng;
    rep(i,n){
        REP(j,i+1,n){
            if(d[i][j]<a[i][j]){
                cout<<-1<<endl;
                return;
            }
            rep(k,n){
                if((k==i)||(k==j))continue;
                if(d[i][k]+d[k][j]==d[i][j]){
                    ng.emplace(i,j);
                }
            }
        }
    }
    ll ans=0;
    rep(i,n){
        REP(j,i+1,n){
            if(ng.count(make_pair(i,j)))continue;
            ans+=d[i][j];
        }
    }
    cout<<ans<<endl;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(15);
    solve();
    return 0;
}


Measured memory_bytes: 3840
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <string>

using namespace std;

int main(void)
{
    int n;
    long long ans = 0;
    cin >>n;

    for(int i = 1; i < n; i++){
        ans += i;
    }

    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin>>n;
  for(int i=1;i<10;i++){
    for(int j=1;j<10;j++){
      if(i*j==n){
        cout<<"Yes";
        return 0;
      }
    }
  }
  cout<<"No";
}

Measured memory_bytes: 256
from itertools import permutations, accumulate
mod = 2019

a = list(map(int,input()))
n = len(a) #入力の桁数

for i in range(n):
    a[i] *= pow(10,n-i-1,mod) #pow(a,b)==a^b べき乗
    
s = [0]+list(accumulate(a)) #accumulate([1,2,3,4,5]) --> 1 3 6 10 15
d = [0]*mod
ans = 0
for i in s:
    j = i%mod
    ans += d[j]
    d[j] += 1
print(ans)

Measured memory_bytes: 26132
#include <stdio.h>

void dump(char *c, int l) {
  for (int i = 0; i < l; i++) {
    printf("%02d: %02d(%c)\n", i, c[i], c[i] + 'a' - 1);
  }
}

int main() {
  char str1[200001];
  char str2[200001];
  
  char alphabets1[26] = {};
  char alphabets2[26] = {};
  
  scanf("%s", str1);
  scanf("%s", str2);
  
  char *s1 = str1;
  char *s2 = str2;
  for(; *s1 != '\0'; s1++, s2++) {
    int i1 = (*s1 - 'a');
    int i2 = (*s2 - 'a');
    //fprintf(stderr, "%c(%02x), %c(%02x)\n", *s1, *s1, *s2, *s2);
    if (
      (alphabets1[i2] == 0 ||
       alphabets1[i2] == i1 + 1) &&
      (alphabets2[i1] == 0 ||
       alphabets2[i1] == i2 + 1)
    ) {
      alphabets2[i1] = i2 + 1;
      alphabets1[i2] = i1 + 1;
    } else {
      puts("No");
      return 0;
    }
  }
  puts("Yes");
  return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const int maxn=1e6+10;
int n;
int a[maxn];
int main(void)
{
    cin>>n;
    for(int i=0;i<n;++i) cin>>a[i];
    bool flag=true;
    unordered_set<int> se;
    for(int i=0;i<n&&flag;++i)
    {
        int now=a[i];
        for(int j=2;j*j<=now&&flag;++j)
            if(now%j==0)
            {
                if(se.count(j)) flag=false;
                se.insert(j);
                while(now%j==0) now/=j;
            }
        if(now>1)
        {
            if(se.count(now)) flag=false;
            se.insert(now);
        }
    }
    if(flag)
    {
        cout<<"pairwise coprime"<<endl;
        return 0;
    }
    se.clear();
    int tmp=a[0];
    for(int i=2;i*i<=tmp;++i)
        if(tmp%i==0)
        {
            se.insert(i);
            while(tmp%i==0) tmp/=i;
        }
    if(tmp>1)
        se.insert(tmp);
    for(int i=1;i<n&&!flag;++i)
    {
        unordered_set<int> se_;
        int now=a[i];
        for(int j=2;j*j<=now;++j)
            if(now%j==0)
            {
                if(se.count(j)) se_.insert(j);
                while(now%j==0) now/=j;
            }
        if(now>1&&se.count(now))
            se_.insert(now);
        if(se_.empty()) flag=true;
        se=se_;
    }
    if(flag)
        cout<<"setwise coprime"<<endl;
    else
        cout<<"not coprime"<<endl;
    return 0;
}

Measured memory_bytes: 7528
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
	int h,n;cin>>h>>n;
	vector<ll> a(n);
	vector<ll> b(n);
	for(int i = 0; i < n; i++) {
		cin>>a[i]>>b[i];
	}
	vector<vector<ll>> dp(h+ 2,vector<ll>(n +1,INF));
	for(int i = 0; i <= n; i++) {
		dp[0][i] = 0;
	}
	for(ll i = 1; i <= h; i++) {
		for(int j = 1; j <= n; j++) {
			if (i - a[j- 1] < 0){
				dp[i][j] = min(dp[i][j - 1],b[j - 1]);
			}
			else{
				dp[i][j] = min(dp[i][j - 1], dp[i - a[j-1]][j] + b[j-1]);
			}
		}
	}
	cout << dp[h][n] << endl;
	return 0;
}

Measured memory_bytes: 81852
<?php
$fp = fopen("php://stdin", "r");
$T=trim(fgets($fp));
$out=3;
$score=0;
$base=array();
while($T>0){
    $input=trim(fgets($fp));
    if($input=="HIT"){
        if(count($base)<3) array_push($base,"x");
        else if(count($base)==3){
            $score++;
            array_shift($base);
            array_push($base,"x");
        }
    }
    else if($input=="HOMERUN"){ $score+=(count($base)+1);$base=array(); }
    if($input=="OUT") $out--;
    if($out==0){
        echo $score."\n";
        $score=0;
        $T--;$out=3;
        $base=array();
    }
}
function Solve($matrix){

}

?>

Measured memory_bytes: 6592
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b[100],ans;
int main(void){
    cin>>a;
    for(int i=0;i<a;i++){
        cin>>b[i];
    }
    sort(b,b+a);
    for(int i=0;i<a-1;i++){
        ans+=b[i];
    }
    if(ans>b[a-1])cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}


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

const int INF = 1000000000;

int main(){
  int m,n,p[10000],c[500],e[500],dp[10000];
  scanf("%d %d",&m,&n);
  for(int i=0;i<m;i++) scanf("%d",p+i);
  for(int i=0;i<n;i++) scanf("%d %d",c+i,e+i);
  sort(p,p+m);
  reverse(p,p+m);
  for(int i=0;i<=n;i++){
    for(int j=m;j>=0;j--){
      if(i==0){
        if(j==0) dp[j] = 0;
        else dp[j] = INF;
      }else if(j-c[i-1]<0){
        dp[j] = min(dp[j],e[i-1]);
      }else{
        dp[j] = min(dp[j],dp[j-c[i-1]]+e[i-1]);
      }
    }
  }
  int ans = 0;
  int sum = 0;
  for(int i=0;i<m;i++){
    sum += p[i];
    ans = max(ans,sum-dp[i+1]);
  }
  printf("%d\n",ans);
  return 0;
}

Measured memory_bytes: 2808
N, K = map(int, input().split())
H = list(map(int, input().split()))

dp = [1000000000] * N
dp[0] = 0
for i in range(N):
    for k in range(1, K+1):
        if i+k >= N:
            break
        dp[i+k] = min(dp[i+k], dp[i] + abs(H[i] - H[i+k]))

print(dp[N-1])

Measured memory_bytes: 52448
S=input()
count=0
for i in range(2,len(S)-1):
  if S[i]=="C" :
    iC=i
    count+=1
temp=[]
if S[0]=="A" and count==1 :
  for i in range(len(S)):
    if i!=0 and i!=iC :
      temp.append(S[i])
  if (''.join(temp)).islower()==True :
    print("AC")
    exit()
print("WA")

Measured memory_bytes: 8984
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,a+r+r*(.5+3**.5*.5j),b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)


Measured memory_bytes: 5924
# coding: utf-8
# Your code here!
#[R,G,B,N] = list(map(int,input().split()))
N = int(input())
#N = 3
num_ab = 0
last_a = 0
top_b = 0
double_ab = 0
#s = ["ABCA",
#"XBAZ",
#"BAD"]
s = []
for i in range(N):
    s.append(str(input()))
for i in range(N):
    num_ab += s[i].count("AB")
    if s[i][0] == "B":
        if s[i][-1] == "A":
            double_ab += 1
        else:
            top_b += 1
    if s[i][-1] == "A":
        if s[i][0] != "B":
            last_a += 1

ans = 0
ans += num_ab
if double_ab > 0:
    ans += double_ab - 1
    if last_a > 0:
        ans += 1
        last_a -= 1
    if top_b > 0:
        ans += 1
        top_b -= 1
    ans += min(last_a,top_b)
else:
    ans += min(last_a,top_b)
print(ans)


Measured memory_bytes: 3700
n = gets.to_i
min = Float::INFINITY
(1..n/2+1).each do |i|
  a = i.to_s.split("").map(&:to_i)
  b = (n-i).to_s.split("").map(&:to_i)
  sum = a.sum+b.sum
  min = sum if min > sum
end
puts min

Measured memory_bytes: 14372
N,M = list(map(int, input().split()))
H = list(map(int, input().split()))

good = [True] * N

for i in range(M):
    A,B = list(map(int, input().split()))
    if H[A-1] > H[B-1]:
        good[B-1] = False
    elif H[A-1] < H[B-1]:
        good[A-1] = False
    elif H[A-1] == H[B-1]:
        good[A-1] = False
        good[B-1] = False

print(good.count(True))

Measured memory_bytes: 84812
#include <iostream>
#include <fstream>

using namespace std;


int main()
{
    string S;
    int cnt = 0;
    int iMin = 99999999;

    int res = 0;

//    std::ifstream in("input.txt");
//    std::cin.rdbuf(in.rdbuf());
    cin >> S;

        for(int i = 0; i < S.size(); i++)
        {
            if(i % 2 == 0 && S[i] != '0')cnt++;
            if(i % 2 == 1 && S[i] != '1')cnt++;
        }
    iMin = min(iMin,cnt);

    cnt = 0;

    for(int i = 0; i < S.size(); i++)
    {
            if(i % 2 == 0 && S[i] != '1')cnt++;
            if(i % 2 == 1 && S[i] != '0')cnt++;
    }
    iMin = min(iMin,cnt);

    cout << iMin <<endl;
    return 0;
}



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

const int MAX = 100005;
int H[MAX];

int main() {
    int N, A, B, h, m;
    m = 0;
    scanf("%d %d %d", &N, &A, &B);
    for (int i = 0; i < N; i++) {
        scanf("%d", &h);
        H[i] = h;
        m = max(m, h / B + 1);
    }

    int mr, ml;
    ml = 0;
    mr = m + 1;
    while (mr > ml) {
        m = (ml + mr) / 2;
        long long p = 0;
        for (int i = 0; i < N; i++) {
            if (H[i] - B * m > 0) {
                p += (H[i] - B * m - 1) / (A - B) + 1;
            }
        }
        if (p <= m) mr = m;
        else ml = m + 1;
    }
    printf("%d\n", mr);
    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define LL long long
int a[100005],b[100005],c[100005];
LL bc[100005];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;++i){
		scanf("%d",&a[i]);
	}
	for(int i=0;i<n;++i){
		scanf("%d",&b[i]);
	}
	for(int i=0;i<n;++i){
		scanf("%d",&c[i]);
	}
	sort(a,a+n);
	sort(b,b+n);
	sort(c,c+n);
	LL sum=0;
	int k=0;
	for(int i=0;i<n;++i){
		while(k<n&&c[k]<=b[i])++k;
		bc[i]=n-k;
	}
	for(int i=n-1;i>=0;--i){
		bc[i]=bc[i+1]+bc[i];
	}
	k=0;
	for(int i=0;i<n;++i){
		while(k<n&&b[k]<=a[i])++k;
		sum+=bc[k];
	}
	printf("%lld\n",sum);
} 

Measured memory_bytes: 2304
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

if sum(B)>sum(A):
  print(-1)
  exit()

amari = []
fusoku = []
for i in range(N):
  if A[i] < B[i]:
    fusoku.append(B[i]-A[i])
  elif A[i] > B[i]:
    amari.append(A[i]-B[i])
amari.sort(reverse=True)
ans = len(fusoku)
nokori = sum(fusoku)
now = 0
while nokori > 0:
  nokori -= amari[now]
  now += 1
  ans += 1
print(ans)
  

  


         

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

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    if (a == b && b == c) {
        cout << 1 << endl;
    } else if(a == b || b == c || a == c) {
        cout << 2 << endl;
    } else {
        cout << 3 << endl;
    }
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long i = 2; i * i <= N; ++i) {
        if (N % i != 0) {
            continue; 
        }
        long long ex = 0; // 指数
        // 割れるだけ割る
        while (N % i == 0) {
            ++ex;
            N /= i;
        }
        // 結果を push
        res.push_back({i, ex});
    }

    // 残った数はそのまま push
    if (N != 1) {
        res.push_back({N, 1});
    } else {
        res.push_back({1, 1});
    }

    return res;
}


int main() {
    long long N, target = 1, ans = 1, num = 1000000007;
    cin >> N;

    vector<long long> ex(N+1, 0); // 指数情報を格納していく
    for (int i = 1; i <= N; ++i) {
        const auto &res = prime_factorize(i); // 素因数分解
        for (auto p : res) {
            ex[p.first] += p.second; 
        }
    }

    for (long long i = 2; i <= N; ++i) {
        ans *= ex[i] + 1 ;
        ans %= num;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
int a[103];
int main()
{
	int n,d=0;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i+=2)	
		if(a[i]%2==1)
			d++;
	cout<<d;
	return 0;
}


Measured memory_bytes: 3592
#include <queue>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <string>
#include <vector>
#include <map>

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef vector<ll> vint;
typedef vector<string> vstr;
typedef pair<ll, ll> pint;
unsigned long long inf = (1LL << 62);
ll mod = 1000000007;

//bool operator< (pint a, pint b) {
	//return a.second < b.second;

//}



ll gcd(ll a, ll b) {

	if (b == 0)
		return a;

	return gcd(b, a % b);


}

ll max(ll a, ll b) {
	if (a < b) {
		return b;
	}
	else
		return a;

}

ll min(ll a, ll b) {
	if (a < b)
		return a;

	return b;
}




pint dx[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

vector<pint> list;










void floyd(int N, ll** d) {

	rep(k, N+1){
		rep(i, N+1) {
			if (d[i+1][k+1] == inf) continue;
			rep(j, N+1) {
				if (d[j+1][k+1] == inf) continue;

				d[i+1][j+1] = min(d[i+1][j+1], d[i+1][k+1] + d[j+1][k+1]);

			}

		}
	}




}


ll vis[100005];
ll d[100005];
vector<pint> M[100005];
vector<ll> anslist;
void dfs(ll K, ll dist) {

	d[K] = dist;
	vis[K] = 1;
	for (int i = 0; i < M[K].size(); i++) {
		if (vis[M[K][i].first] == 0) {
			dfs(M[K][i].first, dist + M[K][i].second);
		}
	}

}


ll a[100005];

int main() {
	ll N, num_kisuu = 0, num_four = 0;

	cin >> N;

	rep(i, N) {
		cin >> a[i];

		
		num_kisuu += (a[i] % 2 == 1) ? 1:0;
		num_four += (a[i] % 4 == 0) ? 1:0;
		
	}
	ll num_guusuu = N - num_kisuu;

	if (num_four >= num_kisuu)
		cout << "Yes" << endl;

	else if (num_four == num_kisuu - 1 && num_guusuu - num_four == 0)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;

	


	return 0;
}

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

int main()
{
	std::string str, str2;
	std::getline(std::cin, str);
	std::getline(std::cin, str2);
	
	int n = str.length(), m = str2.length();
	
	int start = -1;
	
	for (int i = 0; i < n - m + 1; ++i)
	{
		bool flag = true;
		for (int j = i; j - i < m; ++j)
		{
			if (str[j] == str2[j - i] || str[j] == '?')
				continue;
			else
			{
				flag = false;
				break;
			}
		}
		
		if (flag)
			start = i;
	}
	
	if (start == -1)
		std::cout << "UNRESTORABLE";
	else
	{
		for (int i = 0; i < n; ++i)
		{
			if (start == i)
			{
				for (int j = 0; j < m; ++j)
					std::cout << str2[j];
				
				i += m - 1;
			}
			else if (str[i] == '?')
				std::cout << "a";
			else
				std::cout << str[i];
		}
	}
}

Measured memory_bytes: 256