akhauriyash/Code-Regression huggingface dataset:
#include <map>
#include <iostream>
using namespace std;

void C()
{
	map<string, bool> dictionary;
	int N;
	cin >> N;
	char command[20],data[20];
	for (int i = 0; i < N; i++)
	{
		cin >> command;
		cin >> data;

		if (command[0] == 'i')
		{
			string key = data;
			dictionary[key] = true;
		}
		else if (command[0] =='f')
		{
			string key = data;
			if (dictionary.find(key) == dictionary.end())
			{
				cout << "no" << endl;
			}
			else
			{
				cout << "yes" << endl;
			}
		}
	}

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

Measured memory_bytes: 31356
i=int(input())
a=list(sorted(map(int,input().split())))
if i%2==1:
  b=[0]+[u for u in range(2,i,2) for t in range(2)]
  if a==b:
    print((2**(i//2))%(10**9+7))
  else:print(0)
else:
  b=[u for u in range(1,i,2) for t in range(2)]
  if a==b:
    print((2**(i//2))%(10**9+7))
  else:print(0)

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

struct SegmentTree{
private:
    int n;
    std::vector<int> node;

public:
    explicit SegmentTree(int sz){
        n=1;
        while(n<sz)n=n*2;
        node.resize(static_cast<unsigned int>(2 * n - 1), 0);

        for (int i = 0; i <sz ; ++i) node[i+n-1]=0;
        for (int i = n-2; i >= 0 ; --i) node[i]=node[2*i+1]+node[2*i+2];
    }

    void update(int x, int val){
        x+=n-1;
        node[x]+=val;
        while(x>0){
            x=(x-1)/2;
            node[x]=node[2*x+1]+node[2*x+2];
        }
    }

    int getsum(int p,int q,int k=0,int l=0,int r=-1){
        if(r<0)r=n-1;
        if(r<p||l>q)return 0;
        if(p<=l&&r<=q)return node[k];

        return getsum(p,q,2*k+1,l,(l+r)/2)+getsum(p,q,2*k+2,(l+r+1)/2,r);
    }
};

int main(){
    int n, m = 0, q = 0;
    std::cin>>n>>m>>q;
    SegmentTree st(n);
    std::vector<std::pair<int,std::pair<int,std::pair<int,int>>>> d;
    for (int i = 0; i < m; ++i) {
        int l,r;
        std::cin>>l>>r;
        --l;
        --r;
        d.emplace_back(r,std::make_pair(0,std::make_pair(l,i)));
    }
    for (int i = 0; i < q; ++i) {
        int l,r;
        std::cin>>l>>r;
        --l;
        --r;
        d.emplace_back(r,std::make_pair(1,std::make_pair(l,i)));
    }
    std::sort(d.begin(),d.end());
    std::vector<int> ans(q);
    for(auto i:d){
        if(i.second.first==0){
            st.update(i.second.second.first,1);
        }
        else {
            ans[i.second.second.second]=st.getsum(i.second.second.first,i.first);
        }
    }
    for(auto i:ans){
        std::cout<<i<<std::endl;
    }
    return 0;
}

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

for i in range(N):
    v = A[i]
    j = i-1
    
    while j >= 0 and A[j] > v:
        A[j+1] = A[j]
        j -= 1
    
    A[j+1] = v
    print(' '.join([str(n) for n in A]))


Measured memory_bytes: 5608
//Coded by Abhijay Mitra
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <numeric>
#include <vector>
#include <iterator> 
#include <map>
#include <set>
#include <climits>
#include <queue>
#include <cmath>
#include <stack>
#include <cctype>
#include <bitset>
// #include <bits/stdc++.h>
#define double long double
#define int long long int
#define ll int
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
#define bp __builtin_popcount
#define pb push_back
#define res(v) v.resize(unique(v.begin(), v.end()) - v.begin());
#define cnt_res(v) std::distance(v.begin(),std::unique(v.begin(), v.end())); 
#define timer cerr << "Time elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec \n";
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using pii = std::pair<int,int>;
using vpii = std::vector<pii>;
using vvpii = std::vector<vpii>;
#define mp         make_pair
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define per(i,b,a) for (int i = b; i >= a; i--)
#define all(x)     x.begin(), x.end()
using namespace std;
const int N=2e6+10;
const int inf = /*0x3f3f3f3f*/1e18+10;
// const ll M = 998244353 ; // Mulo
// const int M = 1e9+7 ; // Mulo
const double Pi = 3.14159265;
#define F first
#define S second
void solve(){
  int x;cin>>x;
  rep(k,1,inf){
    if(((k*x)%360)==0){cout<<k;return;}
  }
}
int32_t main()
{
  ibs;cti;
  solve()
  /*,cout<<"\n"*/;
  // cout<<"\n";
  int xx=0;
  // int t;cin>>t;while(t--){/*xx++;cout<<"Case "<<xx<<":\n"*/;solve();cout<<"\n";}
  return 0;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,i,m;
  string s;
  cin>>n>>s;
  int a[n],b[n];
  for(i=0;i<n;i++)b[i]=a[i]=s[i]-'0';
  cin>>m;
  for(i=0;i<n;i++){
    if(!m)break;
    if(!a[i]){a[i]++;m--;}
  }
  if(m)for(i=n-1;i>=0;i--){
      if(b[i]==a[i]){
	if(a[i])a[i]=0;
	else a[i]++;
	m--;
      }
      if(!m)break;
    }
  for(i=0;i<n;i++)cout<<a[i];
  cout<<endl;
  return 0;
}
 

Measured memory_bytes: 3216
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Convert;
using static System.Math;
//using static System.Globalization.CultureInfo;

class Program
{
    static void Main(string[] args)
    {
        var nk = Input.ar;
        var xy = Enumerable.Repeat(0, nk[0]).Select(v => Input.arL).ToArray();
        var res = long.MaxValue;
        var xar = xy.OrderBy(v => v[0]).Select(v => v[0]).ToArray();
        var yar = xy.OrderBy(v => v[1]).Select(v => v[1]).ToArray();
        for (var xf = 0; xf < nk[0]; xf++)
            for(var xl=xf;xl<nk[0];xl++)
                for(var yf=0;yf<nk[0];yf++)
                    for(var yl = yf; yl < nk[0]; yl++)
                    {
                        var ct = 0;
                        for (var i = 0; i < nk[0]; i++)
                            if (xar[xf] <= xy[i][0] && xy[i][0] <= xar[xl] && yar[yf] <= xy[i][1] && xy[i][1] <= yar[yl])
                                ct++;
                        if(ct>=nk[1])
                        res = Min(res, (xar[xl] - xar[xf]) * (yar[yl] - yar[yf]));
                    }
        WriteLine(res);
    }
}

public class Input
{
    public static string read => ReadLine();
    public  static int[] ar => Array.ConvertAll(read.Split(' '), int.Parse);
    public  static int num => ToInt32(read);
    public  static long[] arL => Array.ConvertAll(read.Split(' '), long.Parse);
    public  static long numL => ToInt64(read);
    public  const string Alfa = "abcdefghijklmnopqrstuvwxyz";
    public  const int MOD = 1000000007;
}


Measured memory_bytes: 13524
/*
  Motto - try hard to become an expert
*/
#include <bits/stdc++.h>
#include <map>
#include <algorithm>
#include <vector>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <chrono>
#include <thread>
#include <iomanip>
 
//define
#define rep(i,n)    for(int i=0;i<n;i++)
#define repu(i,k,n) for(int i=k;i<=n;i++)
#define repd(i,k,n) for(int i=k;i>=n;i--)
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define INF (int)INT_MAX
#define all(v)  v.begin(), v.end()
#define endl "\n"
 
//typedef
typedef long long int ll;
typedef long double ld;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
typedef std::vector< pii > vii;
typedef std::vector< ll > vll;
typedef std::vector< std::pair < pii, int > > vpp;
 
const int N = 3*1e5 +5 ;
const long long MOD = 998244353;
const long long inf = 1e18;
 
using namespace std;
 
ll MAXN=100001;
ll spf[100001]; 
 
ll modpow(ll x,ll n){
    ll res=1;
    while(n>0){
        if(n&1) res=res*x%MOD;
        x=x*x%MOD;
        n>>=1;
    }
    return res;
}
 
ll modFact(ll n, ll p) 
{ 
    if (n >= p) 
        return 0; 
  
    ll result = 1; 
    for (ll i = 1; i <= n; i++) 
        result = (result * i) % p; 
  
    return result;  
} 
 
bool isPrime(int x)
{
    if(x%2==0)
        return 0;
    for(int i=3;i<=sqrt(x);i+=2)
    {
        if(x%i==0)
            return 0;
    }
    return 1;
}
 

 
void solve()
{
	ll n , a , b ;
	cin>>n>>a>>b;
	ll ans = n/(a+b) * a;
	ll rem = n%(a+b) ;
	if(rem>a){
		ans += a ;
	}
	else{
		ans += rem;
	}
	cout<<ans;
    
}
 
int main() {
    // #ifndef ONLINE_JUDGE
    //     // for getting input from input.txt
    //     freopen("input.txt", "r", stdin);
    //     // for writing output to output.txt
    //     freopen("output.txt", "w", stdout);
    // #endif
    
    // ios_base::sync_with_stdio(0);
    // cin.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--)
    {
        solve();
    } 
    // cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

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

using namespace std;

const int MOD = 1000000007;
const int MAX = 2147483647;
const double PI = 3.14159265358979323846;

int main() {
  int n;
  string a;
  int s[4];
  cin >> n;
  for (int i = 0; i < 4; i++) {
    s[i] = 0;
  }
  for (int i = 0; i < n; i++) {
    cin >> a;
    if (a == "AC") s[0]++;
    if (a == "WA") s[1]++;
    if (a == "TLE") s[2]++;
    if (a == "RE") s[3]++;
  }

  cout << "AC x " << s[0] << endl;
  cout << "WA x " << s[1] << endl;
  cout << "TLE x " << s[2] << endl;
  cout << "RE x " << s[3] << endl;
}


Measured memory_bytes: 3632
import java.util.Scanner;
public class Main {
	static Scanner scan=new Scanner(System.in);
	static int gcd (int a, int b) {return b>0?gcd(b,a%b):a;}
	static long lcm (int a, int b) {return a*b/gcd(a,b);}
	static int max(int a,int b) {return a>b?a:b;}
	static int min(int a,int b) {return a<b?a:b;}
	static long factorial(int i) {return i==1?1:i*factorial(i-1);}
	static int lower_bound(int a[],int key) {
		int low=0,high=a.length;
		while(low<high) {
			int mid=((high-low)/2)+low;
			if(a[mid]<=key)low=mid+1;
			else high=mid;
		}
		return high;
		}
	static int upper_bound(int a[],int key) {
		int low=0,high=a.length;
		while(low<high) {
			int mid=((high-low)/2)+low;
			if(a[mid]<key)low=mid+1;
			else high=mid;
		}
		return high;
		}
	static boolean isPrime (int n) {
		if (n==2) return true;
		if (n<2 || n%2==0) return false;
		double d = Math.sqrt(n);
		for (int i=3; i<=d; i+=2)if(n%i==0){return false;}
		return true;
	}
		public static void main(String[] args) {
			int a=scan.nextInt();
			int b=scan.nextInt();
			System.out.println((a+b)%2==0?(a+b)/2:"IMPOSSIBLE");
		}
}


Measured memory_bytes: 23632
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
typedef long long ll;

int main(){
    string s ; cin >> s;
    if(s[0] == s[1] || s[1] == s[2] || s[0] == s[2]){cout << "No" << endl; return 0;}
    cout << "Yes" << endl; return 0;
}


Measured memory_bytes: 256
def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

N = int_raw()
memo = [{} for x in range(N+1)]

dna = ["A","C","G","T"]

def chk(last4):
    for i in range(len(last4)):
        l = list(last4)
        if i > 0:
            l[i],l[i-1] = l[i-1],l[i]
        if "AGC" in "".join(l):
            return False
    return True

def rec(idx, last3):
    if idx == N:
        return 1
    elif last3 in memo[idx]:
        return memo[idx][last3]
    else:
        ret =0
        for d in dna:
            if chk(last3 + d):
                ret+= rec(idx+1,last3[1:]+d)
                ret = ret % (10**9+7)
        memo[idx][last3] = ret
        return ret


def ans():
    return rec(0,"TTT")

print(ans())


Measured memory_bytes: 3884
fun main(args: Array<String>) {
    val s = readLine()!!
    val even = s.slice(0..s.length-1 step 2)
    val odd = s.slice(1..s.length-1 step 2)

    val ans = Math.min(
        even.count { it=='1' } + odd.count { it=='0' },
        even.count { it=='0' } + odd.count { it=='1' }
    )
    println(ans)

}

Measured memory_bytes: 37368
#include <stdio.h>

int main(void){
  
  int N;
  scanf("%d", &N );
  
  int i;
  long long sum = 0;
  long long wa = 0;
  int A[N];
  int sa[N];
  int ans;
  int shou;
  long long min = 1123456789;
  
  for( i = 0; i < N; i++ ){
    scanf("%d", A+i);
    sum += A[i];
    wa += i+1;
  }
  
  if( sum % wa ) ans = 0;
  else{
    shou = sum/wa;
    for( i = 0; i < N; i++ ){
    sa[i] = A[(i+1)%N] - A[i]-shou;
    }
    
    for( i = 0; i < N-1; i++ ){    
      if( sa[i] <= 0 && !(sa[i] % N))
      ans = 1;
      else{
        ans = 0;
        break;
      }
    }
  }  
  
  
  if( ans ) puts("YES");
  else{     puts("NO");}
  
  return 0;
}

Measured memory_bytes: 896
a, b, c, d = map(int, input().split())
#たかはしのa体力、b攻撃
#あおきのc体力、d攻撃
flag = 0
while(c>0 and a>0):
  c -= b
  if (c<=0):
    flag = 1
  a -= d
  if (a<=0 and c>0):
    flag = 2
if (flag == 1):
  print('Yes')
else:
  print('No')

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

int main() {
  int h, n;
  cin >> h >> n;
  int total = 0;

  rep(i, n) {
    int temp;
    cin >> temp;
    total += temp;
    if (h <= total) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(void) {
  int p, q, r;
  int max;
  
  cin >> p >> q >> r;
  max = p + q;
  max = max < p + r ? max : (p + r);
  max = max < r + q ? max : (r + q);
  
  cout << max << endl;
  
  return 0;
}
  

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0; i<(n); i++)
ll d, c, ans, u;
int main(){
	scanf("%lld", &d);
	for(int i=1; i<=18; i++) rep(j,1<<(i-1)){
		c = d; u = 1;
		int a[20] = {};
		rep(k,i){
			a[k] = c % 10;
			if(j>>k&1){
				a[k] -= 10;
				c += 10;
			}
			if(a[k] < -9 && a[k] > 9) u = 0;
			c /= 10;
		}
		if(c) u = 0;
		rep(k,(i+1)/2){
			if(a[k] + a[i-1-k]) u = 0;
			u *= 10 - abs(a[k]-(!k&&a[0]<=0));
		}
		ans += u;
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 384
#include<iostream>

using namespace std;

// 入力
int A[100];
int N;

// insertion sort
int key,j;

void disp(){
  for(int i=0;i<N;i++)
    if(i==0) cout << A[i];
    else cout << " " << A[i];
  cout << endl;
}
int main(){
  cin >> N;
  for(int i=0;i<N;i++)cin >> A[i];
  disp();
  for(int i=1;i<N;i++){
    key = A[i];
    j = i-1;
    while(j >=0 && A[j] > key){
      A[j+1] = A[j];
      j--;
    }
    A[j+1] = key;
    disp();
  }
}

Measured memory_bytes: 1164
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for(int i = 0;i < (n);++i)
#define RREP(i, n) for(int i = (n)-1; i >= 0; --i)

#define endl '\n'
#define pb push_back
#define eb emplace_back
#define pque priority_queue
#define umap unordered_map
#define BIG 2000000000
#define VERYBIG 1000000000000000ll
#define PI 3.1415926
#define coutdb cout<<fixed<<setprecision(15)

const int dx[]={1,0,-1,0,1,1,-1,-1}, dy[]={0,-1,0,1,1,-1,1,-1};
const long long MOD = 1e9+7;

// typedef int_fast64_t ll;
#define int int_fast64_t

template<typename T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<typename T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template<typename T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template<typename T> inline T nHr(T a,T b){return nCr(a+b-1,b);}

typedef pair<int, int> INTP;
typedef vector<int> INTV;
struct edge2 {int to, cost;};
struct edge3 {int from, to, cost;};

void dijkstra(const vector<vector<edge2> > &G, int s, vector<int> &dist, vector<int> &prev){
  int E = G.size();
  dist.assign(E, VERYBIG); dist[s] = 0;
  prev.assign(E, -1);
  priority_queue<INTP, vector<INTP>, greater<INTP> > que;
  que.push({0, s}); // {dist, index}
  while(!que.empty()){
    INTP p = que.top(); que.pop();
    int v = p.second;
    if(dist[v] < p.first) continue;
    REP(i, G[v].size()){
      edge2 e = G[v][i];
      if(dist[e.to] > dist[v]+e.cost){
        dist[e.to] = dist[v]+e.cost;
        prev[e.to] = v;
        que.push({dist[e.to], e.to});
      }
    }
  }
}

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

  int N, a, b, c, Q, K, x, y; cin >> N;
  vector<vector<edge2> > G(N);
  INTV dist(N), prev(N);
  REP(i, N-1){
    cin >> a >> b >> c;
    a--; b--;
    G[a].pb({b, c}); G[b].pb({a, c});
  }
  cin >> Q >> K; K--;
  dijkstra(G, K, dist, prev);
  REP(i, Q){
    cin >> x >> y; x--; y--;
    cout << dist[x] + dist[y] << endl;
  }
}

Measured memory_bytes: 11888
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);

	static boolean solve() {
		int n = in.nextInt();
		if (n == 0) return false;
		int m = in.nextInt();
		int[] s = new int[m];
		int[] t = new int[m];
		int[] c = new int[m];

		for (int i=0; i<m; i++) {
			String[] str = in.next().split(",");
			s[i] = Integer.parseInt(str[0]);
			t[i] = Integer.parseInt(str[1]);
			c[i] = Integer.parseInt(str[2])/100-1;
		}

		out.println(kruskal(s,t,c,n));
		return true;
	}

	public static int kruskal(int[] s, int[] t, int[] cost, int n) {
		DisjointSet ds = new DisjointSet(n);
		int e = s.length;
		long[] link = new long[e];
		for (int i=0; i<e; i++)
			link[i] = (long)cost[i]<<32 | i;

		int res = 0;

		Arrays.sort(link);
		for (int i=0; i<e; i++) {
			int cur = (int)link[i];
			if (!ds.same(s[cur],t[cur])) {
				ds.unite(s[cur],t[cur]);
				res += cost[cur];
			}
		}

		return res;
	}

	public static void main(String[] args) {
		long start = System.currentTimeMillis();

		while(solve());
		out.flush();

		long end = System.currentTimeMillis();
		//trace(end-start + "ms");
		in.close();
		out.close();
	}

	static void trace(Object... o) { System.out.println(Arrays.deepToString(o));}
}

class DisjointSet {
	int[] data;

	public DisjointSet(int n){
		data = new int[n];
		for (int i=0; i<n; i++) data[i] = i;
	}

	public int find(int x){
		if(data[x] == x) return x;
		return data[x] = find(data[x]);
	}

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

	public void unite(int x,int y){
		if (find(x) == find(y)) return;
		data[find(x)] = find(y);
	}

	public String toString() {
		return Arrays.toString(data);
	}
}

Measured memory_bytes: 40440
#include "bits/stdc++.h"

using namespace std;
using std::vector;

#define ll long long
#define vi vector<int>
#define vl vector<long long>
#define vvi vector<vi>
#define pi  pair<int,int>
#define mp  make_pair
#define pb  push_back
#define MOD int(1e9) + 7
#define PAI  3.1415926535
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define chmax(x, y) x = max(x,y)
#define chmin(x, y) x = min(x,y)
#define pr(x) cout << x << endl
#define Endl endl
#define rep(i, n) for(int i = 0 ; i < n; i++)

const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
const int ddx[8] = {-1,0,1,-1,1,-1,0,1};
const int ddy[8] = {-1,-1,-1,0,0,1,1,1};
const int inf = 99999999;
const ll linf = 1LL << 62;

ll gcd(ll a,ll b){
  if(a < b)swap(a , b);
  if(a % b != 0) return(gcd(b, a%b));
  return b;
}

ll lcm(ll a,ll b){
  if(a < b)swap(a , b);
  return (a / gcd(a , b)) * b;
}

int ans = 0;
ll n;

void check(ll x){

  bool flag_3 = false;
  bool flag_5 = false;
  bool flag_7 = false;

  while(x){
    if(x % 10 == 3)
      flag_3 = true;
    else if(x % 10 == 5)
      flag_5 = true;
    else if(x % 10 == 7)
      flag_7 = true;
    x /= 10;
  }

  if(flag_3 and flag_5 and flag_7)
    ans++;

}

void calc(ll x){
  
  if(x <= n)
    check(x);

  if(x < 100000000){
    calc(x * 10 + 3);
    calc(x * 10 + 5);
    calc(x * 10 + 7);
  }

}

int main(){

  cin >> n;
  calc(0);
  pr(ans);

  return 0;
}


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

typedef pair<int,int> pii;
const int N=2e5+5;
const int MOD=998244353;
int n,m;
int L[15],R[15];
int val[N],dp[N];

inline void add(int &x,int y){
	x+=y;
	if(x>=MOD) x-=MOD;
}

void modify(int x,int v){
	while(x<=n){
		add(val[x],v);
		x+=x&-x;
	}
}

int query(int x){
	int v=0;
	while(x){
		add(v,val[x]);
		x-=x&-x;
	}
	return v;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d",L+i,R+i);
	dp[1]=1;
	modify(1,1);
	for(int i=2;i<=n;i++){
		for(int j=1;j<=m;j++) if(i-L[j]>=1){
			add(dp[i],query(i-L[j])-query(max(0,i-R[j]-1)));
			add(dp[i],MOD);
		}
		modify(i,dp[i]);
	}
	printf("%d\n",dp[n]);
	return 0;
}

Measured memory_bytes: 5384
n,d=map(int,input().split())
l=[[] for i in range(n)]
for i in range(n):
    l[i]=list(map(int,input().split()))
ans=0
for i in range(n):
    for j in range(i+1,n):
        cnt=0
        for k in range(d):
            cnt+=(l[i][k]-l[j][k])**2
        #print(cnt)
        for x in range(1000):
            if x**2==cnt:
                ans+=1
print(ans)

Measured memory_bytes: 3188
// B - 1 Dimensional World's Tale
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define all(x) (x).begin(),(x).end()
#define rp(i,s,e) for(int i=(s);i<(e);++i)

int N,M,X,Y;
vi XX,YY;

bool solve(){
	vector<pair<int,int>> V;//<point,state:[0|1]=[A|B]>
	V.emplace_back(X, 0);
	rp(i,0,N) V.emplace_back(XX[i], 0);
	V.emplace_back(Y, 1);
	rp(i,0,M) V.emplace_back(YY[i], 1);

	sort(all(V));

	int pre_point, pre_state;
	int point, state;
	tie(pre_point, pre_state) = V[0];
	rp(i, 1, V.size()){
		tie(point, state) = V[i];
		if(pre_state > state) return false;
		else if(pre_state < state){
			if(pre_point == point) return false;
		}
		pre_point = point;
		pre_state = state;
	}

	return true;
}

int main(){
	cin>>N>>M>>X>>Y;
	XX.resize(N); rp(i, 0, N) cin>>XX[i];
	YY.resize(M); rp(i, 0, M) cin>>YY[i];
	cout<< (solve()? "No War":"War") <<endl;
}

Measured memory_bytes: 384
#include "bits/stdc++.h"
using namespace std;
const int MAX = 700000;
const int MOD = 1000000007;

long long  fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y){
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}
/*逆元計算*/
long long int  modinv(long long a, long long m) {
	long long int b = m, u = 1, v = 0;
	while (b) {
		long long int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
// index が条件を満たすかどうか
vector<long long int >meguru;
bool isOK(int index, int key) {
	if (meguru[index] >= key) return true;
	else return false;
}
// 汎用的な二分探索のテンプレ
int binary_search(int key) {
	int left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
	int right = (int)meguru.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()
	/* どんな二分探索でもここの書き方を変えずにできる！ */
	while (right - left > 1) {
		int mid = left + (right - left) / 2;

		if (isOK(mid, key)) right = mid;
		else left = mid;
	}
	/* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
	return right;
}
long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

int main() {
	int h, w, k;
	cin >> h >> w >> k;
	vector<string>s;
	int ans = h + w;
	for (int i = 0; i < h; i++) {
		string in;
		cin >> in;
		s.push_back(in);
	}

	for (int bit = 0; bit < (1<<h-1); bit++) {
		int chocolate[10] = {};
		int line = 0;
		int is_OK = 0;
		int sum = 0;
		for (int j = 0; j < h; j++) {
			if (bit & (1<<j)) {
				sum++;
			}
		}
		for (int i = 0; i < w; i++) {
			int a = 0;
			line++;
			for (int j = 0; j < h; j++) {
				if (s[j][i] == '1') {
					chocolate[a]++;
				}
				if (bit & (1<<j)) {
					a++;
				}
			}			

			for (int j = 0; j < h; j++) {
				if (chocolate[j] > k ) {
					if (line == 1) {
						is_OK = 1;
					}
					i = i - 1;
					line = 0;
					sum++;
					for (int l = 0; l <= h; l++) {
						chocolate[l] = 0;
					}
					break;
				}
			}
			if (is_OK == 1) {
				break;
			}
		}
		if (is_OK == 0) {
			ans = min(ans, sum);
		}
	}
	cout << ans;
}

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

using namespace std;

typedef long long lli;
typedef double lld;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<double> vdl;
typedef vector<vector<lli>> mat;
typedef vector<vdl> mad;
typedef unordered_map<lli,unordered_map<lli,lli>> graph;
typedef complex<double> cmp;
typedef vector<cmp> vcl;

lli k;

vll ans;

lli s(lli x){
  lli ret = 0;
  while(x > 0){
    ret += x%10;
    x /= 10;
  }
  return ret;
}

int main(){
  cin >> k;
  lli n = 999999999999999;
  while(n > 0){
    ans.push_back(n);
    for(lli i = 1;i <= n;i*=10){
      if((n-i)*s(n) <= n*s(n-i)){
        n -= i;
        break;
      }
    }
  }
  reverse(ans.begin(),ans.end());
  for(lli i = 0;i < k;i++) cout << ans[i] << endl;
}


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

long long solve(int a, int b, int n, int s) {
	auto ab_max = [](int b, int n) { return n*(b+b-n+1)/2; };
	auto ab_min = [](int a, int n) { return n*(a+a+n-1)/2; };
	if (n == 1) return ((a <= s && s <= b) ? 1 : 0);
	if (n == 2) {
		if (s < 2*a+1 || s > 2*b-1) return 0;
		return int((s + 1) / 2) - max(a, s - b);
	}
	long long ans = 0;
	int m1 = n / 2, m2 = n - m1 - 1;
	for(int c = a + m1; c <= b - m2; c++) {
		int a1 = a, b1 = c-1, a2 = c+1, b2 = b;
		if ((ab_min(a1, m1) + c + ab_min(a2, m2) > s) ||
			(ab_max(b1, m1) + c + ab_max(b2, m2) < s)) continue;
		int s1_min = max(ab_min(a1, m1), s-c-ab_max(b2, m2));
		int s1_max = min(ab_max(b1, m1), s-c-ab_min(a2, m2));
		for(int s1 = s1_min; s1 <= s1_max; s1++) {
			ans += solve(a1, b1, m1, s1) * solve(a2, b2, m2, s-c-s1);
		}
	}
	return ans;
}

int main() {
	while(1) {
		int n, s;
		cin >> n >> s;
		if (n == 0) break;
		cout << solve(0, 100, n, s) << endl;
	}
}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  vector<int>A(N+1);
  A[0]=0;
  for(int i=1;i<N+1;i++)cin>>A[i];
  vector<int>B(N+1);
  B[0]=0;
  for(int i=N;i>0;i--){
    int j=2;
    int s=0;
    while(j*i<=N){
      s+=B[j*i];
      j++;
    }
    if(s%2==A[i]) B[i]=0;
    else B[i]=1;
  }
  int S;
  for(int i=0;i<N+1;i++) if(B[i]==1)S++;
  cout<<S<<endl;
  for(int i=1;i<=N;i++) if(B[i]==1)cout<<i<<" ";
  if(S!=0) cout<<endl;
}

Measured memory_bytes: 2432
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main(){
  int a,b,c;
  cin >> a >> b >> c;
  bool flag = false;
  for(int i=0;i<b;i++){
    if(((i*a)%b) == c){
      flag = true;
      break;
    }
  }
  if(flag){
    cout <<"YES"<<endl;
  }else{
    cout <<"NO"<<endl;
  }
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int d[33]={
    1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51
  };
  int K;
  scanf("%d",&K);
  printf("%d\n",d[K-1]);
  return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<string.h>
#include<ctype.h>
#include<string>
#include<math.h>
#define pi 3.141592653589
#include<iomanip>
using namespace std;

int main(){
     
    string str;
    
    getline(cin,str);
    cout<<"A"<<str[8]<<"C"<<endl;
     
    return 0;
}
 

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <fstream>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <set>
#include <map>
#include <stdlib.h>
#include <string.h>


#define show(x) cerr << "# " << #x << " = " << (x) << endl

#define FOR(i, a, b) for(__typeof(a) i = a; i != b; i++)
#define FR(i, a) FOR(i, 0, a)
#define FOREACH(i, t) FOR(i, t.begin(), t.end())
#define ALL(x) (x).begin(), (x).end()
#define SZ(a) int(a.size())
#define PB push_back
#define MP make_pair
#define F first
#define S second


#define _USE_MATH_DEFINES
using namespace std;

inline bool ascending(int i, int j) { return (i < j); }
inline bool descending(int i, int j) { return (i > j); }

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

const int MN = 1000 + 10;

bool cmp(pair<int ,int > a , pair<int, int >b)
{
	if (a.F == b.F)
		return a.S > b.S;
	return a.F < a.S;
}

int arr[101];

int main(){
    int n ,res =0;
    cin >> n;
    FR(i , n)
        cin >> arr[2*i] >> arr[2*i+1];
    sort(arr , arr+2*n , descending);
    for(int i =0 ; i < n ; i++ )
        res += arr[i*2+1];
    cout << res <<endl;
	return 0;
	
}



Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ldb ldouble

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 19;
int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<n;i++)
#define Se second
#define Fi first

const int MX = 200005;
const int MM = 1000000007;

int main()
{
	int N, M;
	scanf("%d%d", &N, &M);
	ll t = N*100 + M*1800;
	for(int i = 1; i <= M; i++) t = t*2;
	printf("%lld\n", t);
}


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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
//#pragma GCC optimize ("-O3") 
#ifdef YANG33
#include "mydebug.hpp"
#else
#define DD(x) 
#endif
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2019/02/28  Problem: ABC 105 C / Link: http://abc105.contest.atcoder.jp/tasks/abc105_c  ----- */
/* ------問題------



-----問題ここまで----- */
/* -----解説等-----



----解説ここまで---- */
string chng(int n, int t) {

	if (n == 0) return "0";

	string ans = "";
	while (n != 0) {
		int d = n / t; int m = n % t;
		if (m < 0) {
			d++;
			m += -t;
		}
		ans += to_string(m);
		n = d;
	}

	reverse(ALL(ans));
	return ans;

}


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

	LL N; 
	cin >> N;
	string ans = chng(N,-2);
	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 256
//#include <bits/stdc++.h>
//#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<cstring>
#include<bitset>
#include<stack>
#include<time.h>



#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define scd(a) scanf("%d",&a)
#define scdd(a,b) scanf("%d%d",&a,&b)
#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define ALL(x) x.begin(),x.end()
#define sz(a) ((int)a.size())
#define getmid ((l+r)>>1)
#define mst(var,val) memset(var,val,sizeof(var))
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define lowbit(x) x&(-x)
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
#ifdef local
#define dbg(args...) cout << #args << " -> ", err(args);
void err(){ cout << endl; }
template<typename T, typename... Args>
void err(T a, Args... args){ cout << a << ' '; err(args...); }
#else
#define dbg(args...)
#endif // local

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <double, double> pdd;
const int inf=0x3f3f3f3f;
const long long INF=0x3f3f3f3f3f3f3f3fLL;
const double PI=acos(-1.0);
const long double eps=1e-8;
const int mod=998244353;
const int maxn=3e5+100;
const int N=1e6+100;
const int M=500+10;
const ll mm=(1LL<<32);

template <class T>
inline void read(T &x)
{
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar())
        f ^= c == '-';
    for (; isdigit(c); c = getchar())
        x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10)
        ++len;
    for (; len; --len, x %= y, y /= 10)
        putchar(x / y + 48);
}
ll qpow(ll a,ll b,ll mod)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=(ans*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return ans;
}


int main()
{
#ifdef local
    freopen("in.txt","r",stdin);
#endif // local
    IOS;cout.tie(0);
    ll x,k,d;cin>>x>>k>>d;
    if(x<0) x=-x;
    ll dx=x/d,dy=x%d;
    if(dx>=k)
    {
        cout<<x-k*d<<endl;
    }
    else{
        k-=dx;
        if(k&1) cout<<d-dy<<endl;
        else cout<<dy<<endl;
    }
    return 0;
}


Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define pii pair<int,int>
#define pll pair<lli, lli>
#define vi  vector<int>
#define vii vector<pair<int,int>>
#define vll vector<lli>
#define pb  push_back
#define mpr  make_pair
#define ss  second
#define ff  first
#define INF 1000000001
#define inf1 1000000000000000001
#define mod 1000000007
#define pie 3.14159265358979323846264338327950L
#define all(x) x.begin(),x.end()
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define testcase() int tc;cin>>tc;while(tc--)
#define clean(x) memset(x,0,sizeof(x))
const lli maxn = 1e5+9;
vector<lli> catlan(int n) {
    vector<lli> dp(n + 1, 0);
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i ++) {
        for (int j = 0; j < i; ++ j) {
            dp[i] += dp[j] * dp[i - j - 1];
        }
    }
    return dp;
}
lli digit(lli n){int res=(int)log10(n)+1;return res;}
lli lcm(lli a,lli b){lli ans=(a*b)/(__gcd(a,b));return ans;}
lli b_ex(lli n,lli a){lli res=1;while(n){if(n%2==1)res*=a;n>>=1;a=a*a;}return res;}
lli ncr(lli n,lli k){lli ans=1;if(k>n-k)k=n-k;for(lli i=1;i<=k;i++){ans*=(n-i+1),ans=ans/i;}return ans;}
lli power(lli a , lli n){lli ans = 1;while(n){if(n % 2)ans = (ans * a) % mod;n /= 2;a = (a * a) % mod;}return ans;}
lli set_bits(lli n)
{
    int c=0;
    if(n==0)return 0;
    while(n)
    {
        if((n&1)==1)
        {
           cout<<c<<" ";
        }
        c++;
        n=n>>1;
    }
    return c;
}
///=================== ALWAYS CHECK 1 or 0 base case=================================================================================///
///------------------ALWAYS lli-----TEMP TSF99--------------------------------------------------------------------------------------///
int main (){
string a , b , c ;
cin >> a >> b >> c ;
char dif = 'A' - 'a';
printf ("%c%c%c\n" , a [0] + dif , b [0] + dif , c [0] + dif );
return 0;
}



Measured memory_bytes: 3732
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
asum = [0]*(n+1)
bsum = [0]*(m+1)
for i in range(n):
	asum[i+1] = a[i] + asum[i]
for j in range(m): 
	bsum[j+1] = b[j] + bsum[j]
j = m
res = 0
for i in range(n+1):
	if asum[i] > k:
		break
	while asum[i] + bsum[j] > k:
		j-=1
	res = max(res,i+j)
print(res) 



Measured memory_bytes: 47492
#include <iostream>
#include <algorithm>
#include <string>
#include <fstream>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <set>
#include <map>
using namespace std;
typedef long long ll;

// #define DEBUG

void printarray(int n, int a[])
{
    for (int i = 1; i < n + 1; i++)
    {
        cout << a[i];
        if (i != n)
            cout << " ";
    }
    cout << endl;
}

int cycleanalysis(int n, int a[])
{
    int pos, ret, next;
    pos = 0, ret = 0;
    for (int i = 1; i < n + 1; i++)
    {
        pos = i;
        while (a[pos] != pos)
        {
            ret += (a[pos] + a[a[pos]]);
            next = a[pos];
            swap(a[pos], a[a[pos]]);
            pos = next;
        }
    }

    return ret;
}

int main()
{

#ifdef DEBUG
    cout << "DEBUG MODE" << endl;
    ifstream in("input.txt"); //for debug
    cin.rdbuf(in.rdbuf());    //for debug
#endif

    int n, ans;
    cin >> n;
    ans = 0;
    ans += n / 25;
    n %= 25;
    ans += n / 10;
    n %= 10;
    ans += n / 5;
    n %= 5;
    ans += n;
    cout << ans << endl;
    return 0;
}

// getline(cin,s);
// a = strtok(s, ",");  ","で分解
// for (int i = 0; i < n; i++)


Measured memory_bytes: 3120
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define f(i,x,n) for(int i=x;i<n;i++)
#define all(c) c.begin(),c.end()
#define int ll
using ll = long long;
using pii = pair<int,int>;
const int MOD = 1e9+7, N = 1e5 + 10; 

int32_t main(){
   ios::sync_with_stdio(false);
   cin.tie(NULL);
   int n,k;
   cin >> n >> k;
   int ans = 0;
   f(i,k,n+2){
      ans += 1+n*(n+1)/2-(n-i)*(n-i+1)/2-(i-1)*i/2;
      ans %= MOD;
      while(ans<0) ans += MOD;
   }
   cout << ans << '\n';
   return 0;
}


Measured memory_bytes: 3644
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

int n,p[100005];


int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&p[i]);
	int ans=0,tmp=0;
	for (int i=1;i<=n;i++) 
	if (p[i]!=i)
	{
		ans+=(tmp+1)>>1;
		tmp=0;
	}else tmp++;
	ans+=(tmp+1)>>1;
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repe(i, n) for (int i = 0; i <= (n); ++i)
#define repe1(i, n) for (int i = 0; i <= (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
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; }
typedef long long ll;
const int INF = 1e9;
const ll mod = 1000000007;
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main() {
  string s;
  cin >> s;
  if (s[0] == 'Y' && s[1] == 'A' && s[2] == 'K' && s[3] == 'I') {
    cout << "Yes" << "\n";
  } else {
    cout << "No" << "\n";
  }
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<iomanip>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
#define LINF (long long)4e18

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;



int main(){
  ll N,M; cin >> N >> M;
  ll ans = 0;
  if(N >= M/2) ans = M/2;
  else{
    ans += N;
    ans += (M-2*N)/4;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long int 
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int>
#define pi pair<int,int>
#define all(v) v.begin(),v.end()
#define zeros(arr) memset(arr,0,sizeof(arr))
;
#define precise(num)  cout<<fixed; cout << std::setprecision(num)
#define nl cout<<"\n";
#define test int t;cin>>t;wahile(t--) 
const int maxx  = 3*1e5 , limit = 1e17 , MOD=1e9+7;
string binary(int n){bitset<32>b(n) ;string p =b.to_string();return p;}
int decimal(string s){int res = 0; for(int i = 0; i < s.size() ; i++ ){if(s[i] == '1')res = res + pow(2,s.size() - i -1);}    return res;}
bool isPrime(int n){if (n <= 1) return false; if (n <= 3) return true;if (n % 2 == 0 || n % 3 == 0) return false;
for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; }
int pow (int x, int n,int mod) {if (n == 0) return 1; int res = pow (x, n / 2,mod);res = (res * res) % mod;if (n % 2) res = (res * x ) % mod;return res;}
int calcInverse(int a, int n = MOD){int t = 0, newt = 1;int r = n, newr = a;  while (newr != 0) {auto quotient = r /newr;tie(t, newt) = make_tuple(newt, t- quotient * newt);
tie(r, newr) = make_tuple(newr, r - quotient * newr);}if (r > 1)throw runtime_error("a is not invertible");if (t < 0)t += n;t=t%n;    return t;}
#define boost  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int32_t main(){
    boost;
    int n,k;cin>>n;
    int a[n+1][3];
    // int b[n+1];
    // int c[n+1];
    for(int i =0 ; i < n;i++ )cin>>a[i][0]>>a[i][1]>>a[i][2];
    int dp[n+1][3];
    memset(dp,0,sizeof(dp));
    
    dp[0][0]=a[0][0];
    dp[0][1]=a[0][1];
    dp[0][2]=a[0][2];
    for(int i  = 1; i < n ;i ++ ){
        
        for(int k  =0 ; k < 3; k++ ){
            
                dp[i][k] = max(dp[i-1][(k+1)%3] , dp[i-1][(k+2)%3]) +  a[i][k];
        }
        
    }
    
    int ans = max({dp[n-1][0],dp[n-1][1],dp[n-1][2]});
    cout<<ans<<endl;
    
}   

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

int main() {
  int A, B, C, D, L, R;
  cin >> A >> B >> C >> D ;

  L = A + B;
  R = C + D;

  if (L < R) {
    cout << "Right" << endl;
  }
  else if (L > R){
    cout << "Left" << endl;
  }
  else {
    cout << "Balanced" << endl;
  }
}

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

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> s(m, 0);
    vector<int> e(m, 0);
    for(int i = 0; i < m; i++) cin >> s[i] >> e[i];
    //sort(s.begin(), s.end());
    vector<int> number_m1;
    vector<int> number_m2;
  	
  	if(m == 1){
      cout << "IMPOSSIBLE" << endl;
      return 0;
    }
    
  	
    for(int i = 0; i < m; i++){
        if(s[i] == 1 && e[i] != n){
            number_m1.push_back(e[i]);
        }
        if(e[i] == n && s[i] != 1){
            number_m2.push_back(s[i]);
        }
        
    }

    //sort(number_m1.begin(), number_m1.end());
    //sort(number_m2.begin(), number_m2.end());

    //int p = min(, number_m2.size());
    int a[m];
    for(int i = 0; i < m; i++) a[i] = 0; 
    //fill_n(a, m, 0);
    
    //cout << number_m1.size() << endl;
    //cout << number_m2.size() << endl;
    for(int i = 0; i < number_m1.size(); i++){
        a[number_m1[i]-1]++;
        //cout << number_m1[i] << endl;
    }
    for(int i = 0; i < number_m2.size(); i++){
        a[number_m2[i]-1]++;
        //cout << number_m2[i] << endl;
    }
    for(int i = 0; i < m; i++){
        //cout << a[i] << endl;
        if(a[i] > 1){
            cout << "POSSIBLE" << endl;
            return 0;
        }

    }
    cout << "IMPOSSIBLE" << endl;
    
    

}

Measured memory_bytes: 3572
a=input()

if len(a)==1:
  print(0)
  exit()
  
b=a[::2]
c=a[1::2]

b0=b.count("0")
b1=b.count("1")
c0=c.count("0")
c1=c.count("1")

print(min(b0+c1,b1+c0))


Measured memory_bytes: 3188
n,m=map(int,raw_input().split())
graph=[[] for i in xrange(n)]
while m>0:
	m-=1
	a,b=map(int,raw_input().split())
	a-=1
	b-=1
	graph[a].append(b)
	graph[b].append(a)
# print graph
pathcount=0

def dfs(source,l=[]):
	global pathcount
	for i in (graph[source]):
		# print source,graph[source]
		if i not in l:
			l.append(source)
			if len(l)==n:
				pathcount+=1
			# print "exploring ",source," to ",i
			dfs(i,l)
			l.remove(source)
			# print "completed ",source
		# else:
			# print i,"is alrready explored"
	

			
dfs(0,[0])
print pathcount

Measured memory_bytes: 2696
#include <iostream>
#include <string>
#include <algorithm>
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
using namespace std;

int main(void){
	int N;
	cin >> N;
	for(int n=0;n<N;n++){
		string s1,s2,s3;
		cin >> s1 >> s2;
		reverse(s1.begin(),s1.end());
		reverse(s2.begin(),s2.end());
		bool up=false;
		for(int i=0;i<s1.size()||i<s2.size();i++){
			if(i<s1.size()&&i<s2.size()){
				int sum=0;
				if(up)sum++;
				sum+=(s1[i]+s2[i]-'0'-'0');
				s3+=(sum%10)+'0';
				if(sum>=10)
					up=true;
				else
					up=false;
			}else if(i<s1.size()){
				int sum=0;
				if(up)sum++;
				sum+=(s1[i]-'0');
				s3+=(sum%10)+'0';
				if(sum>=10)
					up=true;
				else
					up=false;
			}else if(i<s2.size()){
				int sum=0;
				if(up)sum++;
				sum+=(s2[i]-'0');
				s3+=(sum%10)+'0';
				if(sum>=10)
					up=true;
				else
					up=false;
			}
		}
		if(up)
			s3+='1';
		if(s3.size()>80)
			cout << "overflow" << endl;
		else{
			reverse(s3.begin(),s3.end());
			cout << s3 << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1212
#include <bits/stdc++.h>
#define rep3(i, s, n, a) for (int i = (s); i < (int)(n); i += a)
#define rep2(i, s, n) rep3(i, s, n, 1)
#define rep(i, n) rep2(i, 0, n)

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

int main(){
    int n;
    int k;
    cin >> n >> k;
    vector<int> p;
    int maxint=0;
    rep(i, n){
        int x;
        cin >> x;
        maxint = max(maxint, x);
        p.push_back(x);
    }
    int sum=0;
    vector<int> total(maxint+1);
    rep2(i, 1, maxint+1){
        sum+=i;
        total[i] = sum;
    }
    cout << fixed << setprecision(12) << endl;
    double maxim=0.0;
    rep(i, k){
        maxim += (double)total[p[i]] / p[i];
    }
    double tmp = maxim;
    rep2(i, 1, n-k+1){
        tmp -= (double)total[p[i-1]] / p[i-1];
        tmp += (double)total[p[i+k-1]] / p[i+k-1];
        maxim = max(tmp, maxim);
    }
    cout << maxim << endl;
    return 0;
}

Measured memory_bytes: 4296
#include<bits/stdc++.h>
using namespace std;
int n,k,val[100005],l[100005],r[100005];
vector<int> g[100005];
void die()
{
	cout<<"No"<<endl;
	exit(0);
}
void solve(int v,int p)
{
	l[v]=-1e9-1;
	r[v]=1e9+1;
	if(val[v]!=-1) l[v]=r[v]=val[v];
	for(int i=0;i<g[v].size();i++)
	{
		int to=g[v][i];
		if(to==p)
			continue;
		solve(to,v);
		if(l[to]<-1e8)
			continue;
		if(l[v]<-1e8)
		{
			l[v]=l[to]-1;
			r[v]=r[to]+1;
		}
		else
		{
			if(abs(l[v])%2==abs(l[to])%2)
				die();
			l[v]=max(l[v],l[to]-1);
			r[v]=min(r[v],r[to]+1);
		}
	}
	if(l[v]>r[v])
		die();
}
void make(int v,int p)
{
	for(int i=0;i<g[v].size();i++)
	{
		int to=g[v][i];
		if(to==p)
			continue;
		if(val[to]==-1)
		{
			if(l[to]<=val[v]-1&&val[v]-1<=r[to]) val[to]=val[v]-1;
			else val[to]=val[v]+1;
		}
		make(to,v);
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n-1;i++)
	{
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	memset(val,-1,sizeof(val));
	cin>>k;
	for(int i=1;i<=k;i++)
	{
		int v,p;
		cin>>v>>p;
		val[v]=p;
	}
	solve(1,-1);
	cout<<"Yes"<<endl;
	val[1]=l[1];
	make(1,-1);
	for(int i=1;i<=n;i++)
		cout<<val[i]<<endl;
	return 0;
}


Measured memory_bytes: 15360
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
using namespace std;

int main(){
string s;
cin>>s;
string a=s.substr(0,2),b=s.substr(2,2);

if(stoi(a)>0&&stoi(a)<13&&stoi(b)>0&&stoi(b)<13)cout<<"AMBIGUOUS";
else if(stoi(a)>0&&stoi(a)<13&&stoi(b)>=0&&stoi(b)<100)cout<<"MMYY";
else if(stoi(b)>0&&stoi(b)<13&&stoi(a)>=0&&stoi(a)<100)cout<<"YYMM";
else cout<<"NA";
}


Measured memory_bytes: 256