akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef long double ld;
const double pi=acos(-1.0);
const ll mod=pow(10,9)+7;
const ll INF=pow(2,31)-1;
typedef pair<int,int> P;
typedef vector<int> vi;

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; }

ll gcd(ll a , ll b){
	if(b == 0) return a;
	return gcd(b , a % b);	
}
ll lcm(ll a , ll b){
	ll g = gcd(a , b);
	ll lc = (a/g) * b;
	return lc;
}

int main(){
    ios::sync_with_stdio(false);
    ll x;
    cin >> x;
    int ans=0;
    ll money=100;
    while(money<x){
        money=floor(money*1.01);
        ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3704
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
using namespace std;

int main() {
	ll a, b, k;
	cin >> a >> b >> k;
	if (k <= a) {
		cout << a - k << " " << b << endl;
		return 0;
	}
	else if (k <= a + b) {
		cout << 0 << " " << a + b - k << endl;
		return 0;
	}
	else {
		cout << 0 << " " << 0 << endl;
		return 0;
	}
}

Measured memory_bytes: 256
import math
a, b, x = map(int, input().split())
x = x/a
 
if x <= (a*b) / 2:
    theta = math.atan(b**2 / (2*x))
else:
    theta = math.atan(2*(a*b-x)/(a**2) )
print(math.degrees(theta))

Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
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;
}
const long long INF = 1LL << 60;
ll n;

int main()
{
    cin >> n;
    ll a;
    ll ans[n];
    for (ll i = 0; i < n; i++)ans[i] = 0;
    for (ll i = 1; i < n; i++)
    {
        cin >> a;
        ans[a - 1]++;
    }
    for (ll i = 0; i < n; i++) cout << ans[i] << endl;
    return 0;
}


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

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define each(i, mp) for (auto &i : mp)

template <class T>
inline bool chmax(T &a, T b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmin(T &a, T b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}
const long long INF = 1LL << 60;

const int MAX_N = 110;
const int MAX_V = 100100;

// 入力
int N;
long long W, weight[MAX_N], value[MAX_N]; // 品物の個数は 100 個なので少し余裕持たせてサイズ 110 に

// DPテーブル
long long dp[MAX_N][MAX_V];

int main()
{
  cin >> N >> W;
  for (int i = 0; i < N; ++i)
    cin >> weight[i] >> value[i];

  // 初期化
  for (int i = 0; i < MAX_N; ++i)
    for (int j = 0; j < MAX_V; ++j)
      dp[i][j] = INF;

  // 初期条件
  dp[0][0] = 0;

  // DPループ
  for (int i = 0; i < N; ++i)
  {
    for (int sum_v = 0; sum_v < MAX_V; ++sum_v)
    {

      // i 番目の品物を選ぶ場合
      if (sum_v - value[i] >= 0)
        chmin(dp[i + 1][sum_v], dp[i][sum_v - value[i]] + weight[i]);

      // i 番目の品物を選ばない場合
      chmin(dp[i + 1][sum_v], dp[i][sum_v]);
    }
  }

  // 最適値の出力
  long long res = 0;
  for (int sum_v = 0; sum_v < MAX_V; ++sum_v)
  {
    if (dp[N][sum_v] <= W)
      res = sum_v;
  }
  cout << res << endl;
}

Measured memory_bytes: 86272
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define print(x)cout<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

int main() {
  int n;
  cin >> n;
  vp a(n);
  rep(i,n){
    int x;
    cin >> x;
    a[i] = P(x,i+1);
  }
  sort(rng(a));
  rep(i,n)cout<<a[i].se<<" ";
  cout<<endl;
  return 0;
}

Measured memory_bytes: 4036
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
#define MAX 100000

int d[MAX];
vector<int> V[MAX];
int tt=0,n,m;
queue<int> Q;

void gogo(int x){
  Q.push(x);
  d[x]=tt;
  int v;

  while(!Q.empty()){
    v=Q.front(); Q.pop();
    for(int i=0;i<V[v].size();i++){
      if(d[V[v][i]]==-1) {
        Q.push(V[v][i]);
        d[V[v][i]]=d[v];

      }
    }
  }

}

void gostart(){
  for(int i=0;i<n;i++){
    if(d[i]==-1) {
      gogo(i);
      tt++;
    }
  }
}

int main()  {
  cin>>n>>m;
  for(int i=0;i<n;i++){
    d[i]=-1;
  }

  int s,t;
  for(int i=0;i<m;i++){
    cin>>s>>t;
    V[s].push_back(t);
    V[t].push_back(s);
  }

  gostart();

  int q;
  cin>>q;
  int k,l;
  for(int i=0;i<q;i++){
    cin>>k>>l;
    if(d[k]==d[l]) cout<<"yes"<<endl;
    else cout<<"no"<<endl;
  }
}



Measured memory_bytes: 8988
#include <bits/stdc++.h>
#include <queue>
using namespace std;
int main(void){
    long long N;
    cin >> N;
    long long A,B;
    A = 1;
    queue<long long> a,b;
    
    while(A <= sqrt(N)){
        B = N / A;
        if(N % A == 0) {
            a.push(A);
            /*cout << A << endl;
            cout << B << endl;*/
            b.push(B);
        }
        A++;
    }
    
    queue<long long> c;
    while(!a.empty()){
        c.push(max(a.front(),b.front()));
        a.pop();
        b.pop();
        //cout << c.front() << endl;;
        //c.pop();
    }
    long long T,S;
    T = S = c.front();
    while(!c.empty()){
       if(T >= S){
           T = S;
           c.pop();
           S = c.front();
           //cout << S << T << endl;
       }
    }
    //cout << T << endl;
    long long K = 0;
    while(T > 0){
        T /= 10;
        K++;
    }
    cout << K << endl;
}

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

#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rept(i,k,n) for(ll i = (k); i < (ll)(n); i++)
#define all(v) v.begin(), v.end()
#define Sort(v) sort(v.begin(),v.end())
#define Reverse(v) reverse(v.begin(),v.end())
typedef long long ll;


int ctoi(const char c){
    if('0' <= c && c <= '9') return (c-'0');
    return -1;
}


int main(){
    ll a;
    string b;
    cin>>a>>b;
    ll c=0;
    c+=ctoi(b[0])*100+ctoi(b[2])*10+ctoi(b[3]);
    cout<<a*c/100<<endl;
    return 0;
}


Measured memory_bytes: 3636
import java.util.ArrayList;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();
    int k = sc.nextInt();
    String s = sc.next();


    int diffs = 0;
    char prev = s.charAt(0);
    for (char c : s.toCharArray()) {
      diffs += (prev != c) ? 1 : 0;
      prev = c;
    }
    System.out.println(n - 1 - Math.max(0, diffs - k * 2));
  }
}


Measured memory_bytes: 27752
import sys,collections as cl
Max = sys.maxsize
def l():
	return list(map(int,input.split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[i]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a

a,b,t = m()

print((t//a) * b)

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

int main(){
	long long X, K, D;
	cin >> X >> K >> D;
	long long num = X / D;
	if(abs(num) <= K){
		K -= abs(num);
		X %= D;
	}
	else{
		if(X < 0){
			X += K * D;
			K = 0;
		}
		else{
			X -= K * D;
			K = 0;
		}
	}
	//cout << X << ":" << K << endl;
	if(K % 2){
		if(X < 0) X += D;
		else X -= D;
	}
	cout << abs(X) << endl;
}


Measured memory_bytes: 3628
#include <stdio.h>

int main( void ) {
	int i, j, n, a[ 5 ] = { 10001, 10002, 10003, 10004 }, b[ 12 ], min, tmp;

	for ( scanf( "%d", &n ); n--;  ) {
		scanf( "%d", a + 4 );

		tmp = a[ 4 ];

		if ( a[ 3 ] > tmp ) {
			j = 4;
			do {
				a[ j ] = a[ j - 1 ];

				j--;
			} while ( j && a[ j - 1 ] > tmp );

			a[ j ] = tmp;
		}
	}

	for ( i = 15; i--; )
		if ( i % 5 ) {
			int l = a[ i / 4 ], r = a[ i % 4 ];

			do {
				l *= 10;
			} while ( r /= 10 );

			b[ i - i / 5 - 1 ] = l + a[ i % 4 ];
		}

	for ( i = 0; i < 3; i++ ) {
		min = i;
		for ( j = 11; j > i; j-- )
			if ( b[ j ] < b[ min ] )
				min = j;

		tmp = b[ i ];
		b[ i ] = b[ min ];
		b[ min ] = tmp;
	}

	printf( "%d\n", b[ 2 ] );

	return 0;
}

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

int main(){
    string s;
    cin >> s;

    if(s.length() <= 1 || s.length() % 2 == 1){
        cout << "No" << endl;
        return 0;
    }

    for(int i = 0; i < s.length(); i++){
        if(i % 2 == 0 && s[i] != 'h'){
            cout << "No" << endl;
            return 0;
        }else if(i % 2 == 1 && s[i] != 'i'){
            cout << "No" << endl;
            return 0;
        }
    } 
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const ll INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
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(a>b){a=b;return 1;}return 0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct{template<class T> operator T(){T x;cin>>x;return x;}} IN;
struct before_main_function {
    before_main_function() {
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

// 1-indexed
struct BIT {
    vector<int> data;
    int size;
    BIT(int n): size(n), data(n, 0) {}
    void add(int i, int x) {
        while (i <= size) {
            data[i] += x;
            i += i & -i;
        }
    }
    int sum(int i) {
        int ret = 0;
        while (i > 0) {
            ret += data[i];
            i -= i & -i;
        }
        return ret;
    }
};
signed main() {
    BIT bit(1e5+1);
    int n=IN,q=IN;
    while(q--) {
        int com,x,y;
        cin>>com>>x>>y;
        if(com==0) {
            bit.add(x,y);
        } else {
            int t=bit.sum(y);
            if(x>1) t-=bit.sum(x-1);
            cout<<t<<endl;
        }
    }
    return 0;
}



Measured memory_bytes: 3480
import { readFileSync } from "fs";

const read = () =>
  readFileSync(0, "utf8")
    .split("\n")
    .map((line) => line.split(" "));

const main = (input: string[][]) => {
  const [W, a, b] = input[0].map(Number);

  if (Math.abs(a - b) <= W) {
    return 0;
  }

  return Math.abs(a - b) - W;
};

console.log(main(read()));


Measured memory_bytes: 29664
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ALDS1_2_B
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var a = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var count = 0;

            for(int i = 0; i < n; i++)
            {
                var minj = i;
                for(int j = i; j < n; j++)
                {
                    if(a[j] < a[minj])
                    {
                        minj = j;
                    }
                }

                if( i != minj)
                {
                    var temp = a[i];
                    a[i] = a[minj];
                    a[minj] = temp;
                    count++;
                }
            }

            Console.WriteLine(OutputArray(a));
            Console.WriteLine(count);
        }

        public static string OutputArray<Type>(IEnumerable<Type> array)
            where Type : IComparable
        {
            string aa = "";
            var a = array.ToArray();

            for (int k = 0; k < a.Length; k++)
            {
                aa += a[k];

                if (k != a.Length - 1)
                {
                    aa += " ";
                }
            }

            return aa;
        }
    }
}



Measured memory_bytes: 8252
S = input()
T = input()
count = len(T)
tmp = 0
j = 0
i = len(S) - len(T)

while(i >= 0):
    #print(S[i:i+len(T)])
    #print(T[0:i+len(T)])
    for k in range(len(T)):
        if S[i+k] == T[k]:
            #print("S:"+S[i+k]+" T:"+T[k])
            j += 1
        else:
            #print("j:"+str(j))
            tmp = len(T) - j
            #print("tmp:"+str(tmp))
            if count > tmp:
                count = tmp
            tmp = len(T)
    if len(T) == j:
        count = 0
    i -= 1
    j = 0

print(count)


Measured memory_bytes: 67676
a, b, c, x, y = gets.split.map(&:to_i)
min = Float::INFINITY
n = [x, y].max
0.step(n * 2, 2) do |i|
    cost = c * (n * 2 - i)
    if (n * 2 - i) / 2 < x
        cost += a * (x - (n * 2 - i)/2)
    end
    if (n * 2 - i) / 2 < y
        cost += b * (y - (n * 2 - i)/2)
    end
    min = cost if cost < min
end
puts min


Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
int main(){
  int H, W;
  string line;
  cin >> H >> W;
  vector<string> vec(H);
  for(int i=0;i<H;i++){
    cin >> vec.at(i);
  }
  for(int i=0;i<(W+2);i++){
    line += "#";
  }
  cout << line << endl;
  for(int i=0;i<H;i++){
    cout << "#" << vec.at(i) << "#" << endl;
  }
  cout << line << endl;
}

Measured memory_bytes: 256
from collections import deque
import sys
input = sys.stdin.readline
 
H, W = list(map(int, input().split()))
S = ["#" * (W+2)] + ["#" + input().strip() +
                     "#" for _ in range(H)] + ["#" * (W+2)]
 
ans = 0
 
for j in range(1, H+1):
    for i in range(1, W+1):
        if S[j][i] != ".":
            continue
        m = [[-1] * (W+2) for _ in range(H+2)]
 
        q = deque()
        q.append((j, i, 0))
        m[j][i] = 0
 
        while q:
            y, x, v = q.popleft()
            if ans < v:
                ans = v
            for dj, di in ((y, x+1), (y, x-1), (y+1, x), (y-1, x)):
                if S[dj][di] == "#" or m[dj][di] != -1:
                    continue
                q.append((dj, di, v+1))
                m[dj][di] = v+1
print(ans)

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

int main() {
    int K, X;
    cin >> K >> X;
    int l = X - K + 1;
    int r = X + K;
    for(int i = l; i < r; i++) {
        if(i == l)
            cout << i;
        else
            cout << " " << i;
    }
    cout << endl;
}

Measured memory_bytes: 3600
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
#include <map>
#include <unordered_map>
#include <chrono>
#include <numeric>
using namespace std;
using ll = long long;
const ll INF = (ll)1e18+1;
const ll DIV = 1000000007;
//#define TEST
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
#ifdef TEST
    chrono::system_clock::time_point start, end;
    start = chrono::system_clock::now();
#endif
    long N;
    string S;
    cin >> N;
    cin >> S;
    char alphabet[26] = {'A', 'B', 'C', 'D', 'E', 'F', 'G' ,'H', 'I',
                            'J', 'K', 'L', 'M', 'N', 'O', 'P' ,'Q', 'R',
                            'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
    for(size_t i=0;i<S.size(); i++)
    {
        for(size_t a=0;a<26; a++)
        {
            if(S[i] == alphabet[a])
            {
                if(a + N >= 26) cout << alphabet[a+N-26];
                else cout << alphabet[a+N];
            }
        }
    }
    cout << endl;
#ifdef TEST
    end = chrono::system_clock::now();
    cerr << static_cast<double>(chrono::duration_cast<chrono::microseconds>(end - start).count() / 1000.0) << '[ms]' << endl;
#endif
    return 0;
}

Measured memory_bytes: 256
while True:
    a,b= map(int,input().split())
    if a==0 and b == 0:
        break
    a_rng=list(range(a,0,-1))
    l=0
    li=[]
    for i in a_rng:
        for j in a_rng:
            for k in a_rng:
                if i+j+k ==b and (i!=j and i!=k and j!=k):
                    dd = sorted([i,j,k])
                    if dd not in li:
                        li.append(dd)
                        l+=1
    print(l)


Measured memory_bytes: 5676
#include <bits/stdc++.h>
#pragma GCC diagnostic ignored "-Wunused-result"
#define int long long
using namespace std;

#define fin(i,n) for (int i = 0; i < n; i++)
#define fin2(i,a,b) for (int i = a; i < b; i++)
#define ford(i,n) for (int i = n-1; i >= 0; i--)
#define ford2(i,a,b) for (int i = a-1; i >= b; i--)
 
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define mod 1000000007
#define PI 3.1415926535897932384626
#define EXP1 2.718281828459045
#define BIG 1000000000000000000

#define sl(n) scanf("%lld", &n)
#define sll(n,m) scanf("%lld %lld", &n, &m)
#define slll(n,m,k) scanf("%lld %lld %lld", &n, &m, &k)
#define sllll(n,m,k,o) scanf("%lld %lld %lld %lld", &n, &m, &k, &o)
#define sd(n) scanf("%lf", &n)
#define sdd(n,m) scanf("%lf %lf", &n, &m)
#define sddd(n,m,k) scanf("%lf %lf %lf", &n, &m, &k)
#define sc(c) scanf(" %c", &c)
#define ss(s) scanf("%s", s)
#define sal(t,n) fin(iz,n) { scanf("%lld", &t[iz]); }
#define sad(t,n) fin(iz,n) { scanf("%lf", &t[iz]); }
#define gl(t) scanf(" %[^\n]", t);

#define pc(n) printf("%c\n", n)
#define ps(s) printf("%s\n", s)
#define pss(s) printf("%s\n", s.c_str())
#define pl(n) printf("%lld\n", n)
#define pll(n,m) printf("%lld %lld\n", n, m)
#define plll(n,m,k) printf("%lld %lld %lld\n", n, m, k)
#define pd(n) printf("%lf\n", n)
#define pdd(n,m) printf("%lf %lf\n", n, m)
#define pal(t,n) fin(rz,n) { printf("%lld ", t[rz]); } printf("\n")
#define pad(t,n) fin(rz,n) { printf("%lf ", t[rz]); } printf("\n")

#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
 
#define OK ps("OK")
#define OK1 ps("OK1")
#define OK2 ps("OK2")

#define ll int
#define vl vector<ll>
#define vvl vector<vl>
#define vvvl vector<vvl>

#define dll pair<ll, ll>
#define vdll vector<dll>
#define vvdll vector<vdll>

#define vb vector<bool>
#define vvb vector<vb>
#define vd vector<double>
#define vvd vector<vd>
#define vc vector<char>
#define vvc vector<vc>

#define all(v) v.begin(), v.end()
#define vlen(v) (int)(v.size())
#define pb push_back
#define fi first
#define se second

const int bm = (int)(1e5) + 5;
vl dp, tmp;
int n, w;

signed main()
{
    sll(n, w);
    dp.assign(bm, BIG);
    dp[0] = 0;
    tmp = dp;
    fin(i, n) {
        int po, val;
        sll(po, val);
        fin(i, bm) {
            chmin(tmp[i], dp[max(0LL, i-val)] + po);
        }
        ford(i, bm-1) {
            chmin(tmp[i], tmp[i+1]);
        }
        dp = tmp;
    }
    ford(i, bm) if (dp[i] <= w) {
        pl(i); break;
    }
}

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

struct Node {
	std::vector<Node*> prev;
	std::vector<Node*> next;
	std::vector<int> dist;
	std::vector<int> pdist;
	long long x;
	bool check;
	Node() : prev(std::vector<Node*>()), next(std::vector<Node*>()), dist(std::vector<int>()), pdist(std::vector<int>()), check(false), x(-0xFFFFFFF){}
	Node(Node& n) : prev(n.prev), next(n.next), dist(n.dist), pdist(n.pdist), check(n.check), x(n.x){}
};

void search(Node *n, bool *b) {
	n->check = true;
	for (unsigned int i = 0; i < n->next.size(); i++) {
		if (n->next[i]->x == -0xFFFFFFF) {
			n->next[i]->x = n->x + n->dist[i];
		}
		else {
			if (n->next[i]->x != n->x + n->dist[i]) {
				*b = false;
				return;
			}
		}
	}
	for (unsigned int i = 0; i < n->prev.size(); i++) {
		if (n->prev[i]->x == -0xFFFFFFF) {
			n->prev[i]->x = n->x + n->pdist[i];
		}
		else {
			if (n->prev[i]->x != n->x + n->pdist[i]) {
				*b = false;
				return;
			}
		}

	}
	for (unsigned int i = 0; i < n->next.size(); i++) {
		if (!n->next[i]->check) {
			search(n->next[i], b);
		}
	}
	for (unsigned int i = 0; i < n->prev.size(); i++) {
		if (!n->prev[i]->check) {
			search(n->prev[i], b);
		}
	}
	return;
}

int main() {
	int N, M;
	std::cin >> N >> M;
	int first = 0;

	std::vector<Node> g(N);

	for (int i = 0; i < M; i++) {
		int l,r,d;
		std::cin >> l >> r >> d;
		l--; r--;

		g[l].next.push_back(&g[r]);
		g[r].prev.push_back(&g[l]);
		g[l].dist.push_back(d);
		g[r].pdist.push_back(-d);
	}

	bool pass = true;
	for (int i = 0; i < N; i++) {
		if (!g[i].check) {
			g[i].x = 0;
			search(&g[i], &pass);
		}
	}
	if (pass) {
		std::cout << "Yes" << std::endl;
	}
	else {
		std::cout << "No" << std::endl;
	}
	return 0;
}

Measured memory_bytes: 28160
using System;
using System.Linq;

class C
{
	static void Main()
	{
		Console.ReadLine();
		var a = Console.ReadLine().Split().Select(int.Parse).ToArray();
		a = a.OrderByDescending(x => x).GroupBy(x => x).OrderByDescending(g => g.Count()).SelectMany(g => g.Take(2)).ToArray();

		var M = a[1];
		for (int j = 2; j < a.Length; j++)
			if ((M = Gcd(M, a[j])) == 1) break;

		for (int i = 1; i < a.Length; i++)
		{
			var g = a[0];
			for (int j = 1; j < a.Length; j++)
			{
				if (j == i) continue;
				if ((g = Gcd(g, a[j])) <= M) break;
			}
			M = Math.Max(M, g);
		}
		Console.WriteLine(M);
	}

	static int Gcd(int x, int y) { for (int r; (r = x % y) > 0; x = y, y = r) ; return y; }
}


Measured memory_bytes: 31836
A,B,M=map(int,input().split())
L_A=list(map(int,input().split()))
L_B=list(map(int,input().split()))
ans=min(L_A)+min(L_B)
for i in range(M):
	X,Y,Z=map(int,input().split())
	ans=min(ans,(L_A[X-1]+L_B[Y-1]-Z))
print(ans)

Measured memory_bytes: 18736
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
string s[maxn];
int main()
{
	int n;
	int d=0,a=0,b=0,ab=0;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>s[i];
	}
	for(int i=0;i<n;i++)
	{
		for(int j=1;j<s[i].size();j++)
		{
			if(s[i][j-1]=='A'&&s[i][j]=='B')
			{
				d++;
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		if(s[i][0]=='B') b++;
		if(s[i][s[i].size()-1]=='A') a++;
		if(s[i][0]=='B'&&s[i][s[i].size()-1]=='A') ab++;
	}
	int ans=0;
	ans=d+min(b,a);
	if(b==a&&b==ab&&b!=0) ans--;
//	cout<<a<<" "<<b<<endl;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
#define IO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)

using namespace std;
int M, X;

int main(void){
	//IO("test.in", "test.out");
	M = 1;
	scanf("%d", &X);
	for(int i = 2; i <= X; i++){
		int n = 2;
		while((int)pow(i, n) <= X){
			if((int)pow(i, n) > M) M = (int)pow(i, n);
			n++;
		}
	}
	printf("%d\n", M);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int a[55];
int main(){
    int n, k, ans = 0;
    scanf("%d%d", &n, &k);   
    for(int i=1;i<=n;i++) scanf("%d", &a[i]);
    for(int i=0;i<=n;i++){
        for(int j=i+1;j<=n+1;j++){
            int l = i, r = n-j+1;
            if(l+r > k) continue;
            int d = k-(l+r);
            vector<int> v;
            for(int x=1;x<=i;x++) v.push_back(a[x]);
            for(int x=j;x<=n;x++) v.push_back(a[x]);
            sort(v.begin(), v.end());
            int sum = 0;
            for(int i=0;i<v.size();i++) sum += v[i];
            for(int i=0;i<min((int)v.size(), d);i++){
                if(v[i] < 0) sum -= v[i];
            }
            ans = max(ans, sum);
        }
    }
    printf("%d\n", ans);
}

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

int main(){
  int num;
  cin >> num;
  long long sum = 0;
  for(int i=0;i<=num;i++){
    if(i%3 == 0 && i%5 == 0){
      continue;
    }
    else if(i%3 == 0){
      continue;
    }
    else if(i%5 == 0){
      continue;
    }
    else {
      sum +=i;
    }
  }
  cout << sum << endl;
}

Measured memory_bytes: 3624
from functools import reduce
from operator import mul
import math


def end_of_loop():
    raise StopIteration


def main():
    N, K = map(int, input().split())
    print(sum(reduce(mul, (0.5
                           if i << j < K
                           else end_of_loop()
                           for j in range(int(math.log2(K))+2)), 1 / N)
              for i in range(1, N + 1)))
    return


main()


Measured memory_bytes: 3684
#include<stdio.h>
int main(){
    int x, y, W, H, r;
    scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);
    if (0<=x-r && x+r<=W && 0<=y-r && y+r<=H){
		printf("Yes\n");
	}else{
		printf("No\n");
	}
    return 0;
}


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

int main()
{
	ios_base::sync_with_stdio(false);
 	cin.tie(NULL);
	
	int n;
	cin >> n;
	vector < int > h(n+1);
	for(int i=1; i<=n; i++)
		cin >> h[i];
	vector < int > dp(n+1);
	dp[2] = abs(h[2]-h[1]);
	for(int i=3; i<=n; i++)
		dp[i] = min(dp[i-1] + abs(h[i]-h[i-1]), dp[i-2] + abs(h[i]-h[i-2]));
	cout << dp[n] << endl;
	
	return 0;
}

Measured memory_bytes: 1024
A,B,K = map(int,input().split())
i = 1
cnt = 0
num = []
for i in range(1,min(A,B)+1,1):
  if (A % i) == 0 and (B % i) == 0:
    num.append(i)
    cnt += 1
num.sort(reverse=True)
print(num[K-1])

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <string>
#include <map>
#include <algorithm>
using namespace std;


int main()
{
	int n, k;
	cin >> n >> k;

	if(k==1)
		cout << 0 << endl;
	else
		cout << n-k << endl;

	return 0;
}

Measured memory_bytes: 256
//
// Created on 2020/02/16.
//

//#include <bits/stdc++.h>
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <ios>
#include <iomanip>
#include <numeric>

#define all(x) (x).begin(),(x).end()
typedef long long ll;
using namespace std;
const long long LINF =1e18;
const int INF = 1e9;
using gragh = vector<vector<int>>;

int main() {
    string ans ="APPROVED";
    int n;
    cin>>n;

    for (int i = 0; i < n; ++i) {
        int temp;
        cin>>temp;
        if(temp%2==0){
            if(temp%3==0){
                continue;

            }
            else if(temp%5==0) continue;
            ans ="DENIED";
        }
    }


    cout<<ans<<endl;
}


Measured memory_bytes: 384
n = int(input())
ap = bp = 0
for i in range(n):
  a, b = map(str, input().split())
  if(a > b):
    ap = ap + 3
  elif(a < b):
    bp = bp + 3
  else:
    ap = ap + 1
    bp = bp + 1
print(ap, bp)


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

int main(){
	int E, O;
	scanf ("%d %d", &E, &O);
	int sum = 0;
	for (int i=1; i<E; i++){
		sum+=i;
	}
	for (int i=1; i<O; i++){
		sum+=i;
	}
	printf ("%d", sum);


return 0;
}

Measured memory_bytes: 1700
import sys
from math import*
for e in sys.stdin:
 a,b,c,d,x,y=map(float,e.split(','))
 g=-2*(atan2(y-b,x-a)-atan2(d-b,c-a));s,t=sin(g),cos(g);x-=a;y-=b
 print(f'{t*x-s*y+a:.6f} {s*x+t*y+b:.6f}')


Measured memory_bytes: 5764
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define dup(x,y) (((x)+(y)-1)/(y))
#define v(T) vector<T>
#define vv(T) v(v(T))
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<pii> vp;
typedef vector<T> vt;
inline int getInt() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MX = 200005;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
//---------------------------------------------------------------
#define fastio cin.tie(nullptr); std::ios::sync_with_stdio(false);
#define myio ifstream iofi; if(argc>1){iofi.open(argv[1]); std::cin.rdbuf(iofi.rdbuf());}
//--------------------------------------------------------------

void Main(){
  int n,k;
  cin>>n>>k;
  v(char) d(k);
  cin>>d;
  srep(i,n,100000){
    string s = to_string(i);
    bool f = true;
    rep(j,s.length()){
      rep(p,k){
        if(d[p]==s[j]){f = false; break;}
      }
      if(!f) break;
    }
    if(f){cout<<s<<endl; return;}
  }
  exit(1);
} int main(int argc,char** argv)
{fastio; myio; Main();}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cmath>

using namespace std;
using ll = long long;

int gcd(int a, int b) { return (b == 0) ? a : gcd(b, a % b); }

#define CIN(T, x) T x; cin >> x;
#define CINS(T, x, N) vector<T> x(N); for(int i = 0; i < (N); i++) { cin >> x[i]; }
#define SHOW(x) for(int i = 0; i < x.size(); i++) { cout << x[i] << " "; } cout << "\n";
#define SHOW2(x) for(int j = 0; j < x.size(); j++) { SHOW(x[j]); } cout << "\n";


int main() {

    CIN(ll, N);

    ll A = N;
    for (int i = sqrt(N); i > 0; i--) {
        if ( N % i == 0 ) {
            A = N / i;
            break;
        }
    }

    int count = 1;
    for (int i = 0; i < A; i++) {
        if ( A >= 10 ) {
            A /= 10;
            count++;
        }
    }

    cout << count << "\n";

    return 0;
}

Measured memory_bytes: 256
#６回目、2020-0612
#2重ループ　＋O(1)
#場合分けを近道と通常のみ（絶対値を使う）

#初期入力
N, x, y = map(int, input().split())
normal =0
short =0
ans ={i:0 for i in range(1,N)}
for i in range(1,N):
    for j in range(i+1,N+1):
         normal =j -i
         short  =abs(x-i) +1 +abs(j-y)
         dist =min(normal,short)
         ans[dist] +=1
      

#答え出力
for i in range(1,N):        
    print(ans[i])

Measured memory_bytes: 3572
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#include <deque>
using bint = boost::multiprecision::cpp_int;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repSE(i,s,n) for (int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
    int K;
    cin >> K;
    deque<ll> que;
    repSE(i,1,10) que.push_back(i);
    int i = 9, cnt = 3;
    ll x, ret;
    if (K <= 9) {
        ret = K;
    }
    else {
        while(i < K) {
            if (cnt == 3) {
                x = que.front();
                que.pop_front();
                if (x % 10 != 0) {
                    que.push_back(10 * x + x % 10 - 1);
                    i++;
                }
                cnt = 1;
            }
            else if (cnt == 1) {
                que.push_back(10 * x + x % 10);
                i++;
                cnt = 2;
            }
            else if (cnt == 2) {
                if (x % 10 != 9) {
                    que.push_back(10 * x + x % 10 + 1);
                    i++;
                }
                cnt = 3;
            }
        }
        ret = que.back();
    }
    cout << ret << endl;
    return 0;
}


Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
#define Priq priority_queue<int,vi,greater<int>>
#define pb push_back
#define mp make_pair
#define INF (1ll<<60)
signed main(){
  int N; cin>>N;
  vi A(N);
  rep(i,0,N) cin>>A[i];
  sort(ALL(A));
  if(A[N-1]-A[0]==0){
    int X=A[0];
    if(X+1==N||N>=X*2) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
  }
  else if(A[N-1]-A[0]==1){
    int P=A[0],Q=A[N-1],R=0,S=0;
    rep(i,0,N){
      if(A[i]==P) R++;
      else S++;
    }
    if(P==R) cout<<"Yes"<<endl;
    else if(P>=R&&(Q-R)*2<=S) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
  }
  else cout<<"No"<<endl;
  }




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

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

fn main() {
    let n: u64 = read();
    let a: u64 = read();
    let b: u64 = read();

    let elems = n / (a + b);
    let modulo = n % (a + b);

    let ans;
    if modulo == 0 {
      ans = elems * a;
    } else if modulo < a {
      ans = elems * a + modulo;
    } else {
      ans = elems * a + a;
    }
    println!("{:?}", ans);
}


Measured memory_bytes: 4352
#include<stdio.h>
#define N 100000

typedef struct data{
  char name[100];
  int t;
}D;

D Q[N];
int head ,tail,n;
void enq(D);
D deq();
int min(int,int);

int main(){
  int n,q,i,time,total=0;
  D que;
  scanf("%d %d",&n,&q);
  for(i=1;i<=n;i++){
    scanf("%s",Q[i].name);
    scanf("%d",&Q[i].t);
  }
  head=1;
  tail=n+1;
  while(head!=tail){
    que=deq();
    time=min(q,que.t);
    que.t-=time;
    total+=time;
    if(que.t>0)enq(que);
    else printf("%s %d\n",que.name,total);
  }
  return 0;
}

void enq(D que){
  Q[tail]=que;
  tail=(tail+1)%N;
}

D deq(){
  D x=Q[head];
  head=(head+1)%N;
  return x;
}

int min(int x,int y){
  if(x>y)return y;
  else return x;
}



Measured memory_bytes: 11980
#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
#define fo(i,n) for(int i=0;i<n;++i)
#define Fo(i,k,n) for(int i=k;i<n;++i)
typedef long long int lli;
int main(){
    FIO
    int N,D; cin>>N>>D;
    int i,ans=0;
    fo(i,N){
        double X,Y,res;
        cin>>X>>Y;
        res=sqrt(X*X+Y*Y);
        if(res<=D){
                ans++;
        }
    }
    cout<<ans<<endl;
}


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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int d;
  cin >> d;
  vector<int> c(26);
  for (int i = 0; i < 26; i++) {
    cin >> c[i];
  }
  vector<vector<int>> s(d, vector<int>(26));
  for (int i = 0; i < d; i++) {
    for (int j = 0; j < 26; j++) {
      cin >> s[i][j];
    }
  }
  vector<int> t(d);
  for (int i = 0; i < d; i++) {
    cin >> t[i];
  }
  vector<int> v(d);
  for (int i = 0; i < d; i++) {
    v[i] += s[i][t[i] - 1];
    for (int j = 0; j < 26; j++) {
      int last = 0;
      for (int k = i; k >= 0; k--) {
        if (t[k] - 1 == j) {
          last = k + 1;
          break;
        }
      }
      v[i] -= c[j] * (i + 1 - last);
    }
    if (i != d - 1) {
      v[i + 1] = v[i];
    }
  }
  for (int i = 0; i < d; i++) {
    cout << v[i] << '\n';
  }
  return 0;
}

Measured memory_bytes: 3684
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
  int N; cin >> N;
  vector<int> a(N);
  for(int i = 0;i < N;++i) {
    cin >> a[i];
  }
  int b = *max_element(a.begin(), a.end());
  int c = *min_element(a.begin(), a.end());
  int d = b - c;
  cout << d << endl; 
}

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

using namespace std;

int main (){

    string S;
    cin >> S;

    int price = 700;
    if (S[0] == 'o') {
      price += 100;}
    if (S[1] == 'o'){
      price += 100;}
    if (S[2] == 'o') 
    {price += 100;}

    cout << price << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <vector>
#include <bitset>
#include <queue>
using namespace std;

int main(){
    int N, M;
    cin >> N >> M;
    int a[M], b[M];
    N++;
    int anss[N];
    for(int i = 0; i < N; i++){
        anss[i] = 0;
    }
    for(int i = 0; i < M; i++){
        cin >> a[i] >> b[i];
        anss[a[i]]++;
        anss[b[i]]++;
    }
    for(int i = 1; i < N; i++){
        cout << anss[i] << endl;
    }


    return 0;
}

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

using namespace std;

int main() {

    int A, B, C, X, ans=0;

    cin >> A >> B >> C >> X;


    for(int p=0; p<=A; p++) {
        for(int q=0; q<=B; q++){
            for(int r=0; r<=C; r++){
                if((500*p+100*q+50*r) == X){
                    ans++;
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import sys


def input():
    return sys.stdin.readline().strip()


N = int(input())
L = list(map(int, input().split()))

L.sort()

ans = 0
# a(一番短い辺)を固定して，b, cで尺取
for a in range(N):
    c = a + 1
    for b in range(a + 1, N):
        while c < N and L[c] < L[a] + L[b]:
            c += 1
        ans += c - (b + 1)

print(ans)


Measured memory_bytes: 3188
#include <stdio.h>
#include <string.h>
 
char s[100001];
char * word[] = {"dream", "dreamer", "erase", "eraser"};
char dp[100001];
int main(){
    memset(dp,0,sizeof(dp));
    scanf("%s", s);
 
    int len = strlen(s);
    int index = 0;
    
    dp[0] = 1;
    for(int index = 0; index < len; index++){
        if(dp[index] == 0){
            continue;
        }
        for(int i = 0; i < 4; i++){
            if(strncmp(word[i],s+index,strlen(word[i])) == 0){
                dp[index+strlen(word[i])] = 1;
            }
        }
    }
    puts(dp[len]?"YES":"NO");
}

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

const int N = 1e5 + 10;

int n, k, c, ans, cnt, a[N];

int main(){
	cin >> n >> c >> k;
	for(int i = 1; i <= n; ++ i){
		cin >> a[i];
	}
	sort(a + 1, a + n + 1);
	int bg = -1;
	for(int i = 1; i <= n; ++ i){
		if(bg != -1 && (a[i] - bg > k || cnt == c)){
			bg = -1;
			cnt = 0;
		} 
		if(bg == -1) {
			bg = a[i];
			ans ++;
		}
		if(a[i] - bg <= k && cnt < c){
			cnt ++;
		}
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 640
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <complex>
#include <cstdint>
#include <tuple>
#include <numeric>
#define M_PI       3.14159265358979323846


using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define FILL(a, x) memset(a, x, sizeof(a))

//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)

const LL MOD = 1000000007;

const int N = 2005;
char board[N][N];
int xx[N][N], yy[N][N];

int main() {
	int h,w;
	scanf("%d%d", &h, &w);
	REP(i, h)scanf("%s", &board[i+1][1]);
	REP(i, h + 2)board[i][0] = board[i][w + 1] = '#';
	REP(i, w + 2)board[0][i] = board[h+1][i] = '#';
	FOR(i, 1, h + 1) {
	int sx = 1;
		while (sx <= w) {
			int tx = sx;
			while (board[i][tx] == '.')tx++;
			FOR(k, sx, tx)xx[i][k] = tx - sx;
			sx = tx + 1;
		}
	}
	FOR(i, 1, w + 1) {
		int sy = 1;
		while (sy <= h) {
			int ty = sy;
			while (board[ty][i] == '.')ty++;
			FOR(k, sy, ty)yy[k][i] = ty - sy;
			sy = ty + 1;
		}
	}
	int ret = 0;
	FOR(i, 1, h+1)FOR(j, 1, w+1)ret = max(ret, xx[i][j] + yy[i][j]-1);
	printf("%d\n", ret);
	return 0;
}

Measured memory_bytes: 35584
#1<=Dまでの数全てにおいて、+Dしたときの経路コストを求める
#これは１つの数につき１度しか走らないのでO(N)=O(90000)

H,W,D=map(int,input().split())
A=[-1 for j in range(H*W)]
for j in range(H):
    inp=map(int,input().split())
    for r,i in enumerate(inp):
        
        A[i-1]=(j,r) #1は0

cost=[-1 for j in range(H*W)]    
for j in range(0,D):
    i=j
    cost[i]=0
    while True:
        i+=D
        if(i>=H*W):
            break

        cost[i]=cost[i-D]+abs(A[i][0]-A[i-D][0])+abs(A[i][1]-A[i-D][1])


Q=int(input())
for j in range(Q):
    l,r=map(int,input().split())
    print(cost[r-1]-cost[l-1])


Measured memory_bytes: 14436
import math
N,M = map(int,input().split())
ans = 0
for i in range(math.ceil(math.sqrt(M)),0,-1):
    if M%i == 0:
        j = M//i    #i<=j
        if N<=i:
            ans = max(ans,j)
        if N<=j:
            ans = max(ans,i)
print(ans)


Measured memory_bytes: 3060
#include <algorithm>
#include <climits>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <vector>

using namespace std;
constexpr long long int INF = std::numeric_limits<long long int>::max();
constexpr long long int NINF = std::numeric_limits<long long int>::min();
#define int long long int

void solve() {
  int A, B;
  cin >> A >> B;
  cout << A + B / 2 << endl;
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
  return 0;
}


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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef map<ll,ll>::iterator itll;
typedef long double ld;
typedef map<ll,ll> mapll;

#define con continue
#define pb push_back
#define fi first
#define se second
#define fr front()
#define one 1.0
#define inf 1000000000000000000
#define all(vl) vl.begin(),vl.end()
#define m_p make_pair 
#define sz(a) sizeof(a)
#define forn(mp,it) for(it = mp.begin();it!=mp.end();it++)
#define FOR(i,a,n) for(int i=a;i<n;i++) 
#define FORE(i,a,n) FOR(i,a,n+1)
#define Endl endl
#define eNdl endl
#define enDl endl
#define endL endl
#define PI 3.14159265358979323846

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll n,m,k,ans = 0;
	cin>>n>>m>>k;
	vector<string> vs(n),an;
	for(int i=0;i<n;i++)cin>>vs[i];
	an = vs;
	map<P,ll> mp;
	for(ll ind = 0;ind<(1<<n);ind++)
	{
		for(ll ind1 = 0;ind1<(1<<m);ind1++)
		{
			vs = an;
			vector<ll> vl,vl1;
			for(int i=0;i<n;i++)
			{
				if(ind&(1<<i))vl.pb(i);
			}
			for(int i=0;i<m;i++)
			{
				if(ind1&(1<<i))vl1.pb(i);
			}
			for(int i=0;i<vl.size();i++)
			{
				for(int j=0;j<m;j++)
					vs[vl[i]][j] = '.';
			}
			for(int i=0;i<vl1.size();i++)
			{
				for(int j=0;j<n;j++)
					vs[j][vl1[i]] = '.';
			}
			ll cnt = 0;
			for(int i=0;i<n;i++)
			{
				for(int j=0;j<m;j++)cnt+=vs[i][j] == '#';
			}
			if(mp[P(ind,ind1)])
				cnt = -inf;
			ans+=(cnt == k);
			mp[P(ind,ind1)]++;
		}
	 } 
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3888
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;

int main(void) {
    ll n,m;
    cin>>n>>m;
    int balls[n];
    bool flg[n]={};
    rep(i,n){balls[i]=1;}
    flg[0]=true;
    rep(i,m){
        int t,s;
        cin>>t>>s;
        t--;s--;
        balls[s]++;
        if(flg[t]){flg[s]=true;}
        balls[t]--;
        if(balls[t]==0){flg[t]=false;}
    }
    int res=0;
    rep(i,n){
        res += int(flg[i]);
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	long long a, b, k;
	cin >> a >> b >> k;

	if(a>=k)
		cout << a - k << " " << b << endl;
	else if(a+b>=k)
		cout << 0 << " " << b - k + a << endl;
	else
		cout << 0 << " " << 0 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    
    //*
    int a, b;
    cin >> a >> b ;
    //*/

    /*
    vector<int> vec(3);
    cin >> vec.at(0) >> vec.at(1) >> vec.at(2) ;

    sort(vec.begin(), vec.end());
    //*/
    
    //Sunny, Cloudy, Rainy
    /*
    if( a < 10 && b < 10 ){
        cout << a * b << endl;
    } else {
        cout << -1 << endl;
    }
    //*/
    
    cout << b + 100 * ( 10 - min(a, 10) ) << endl;
    
    //printf("%lf\n", ((a / 2 + a % 2) / a));

    return 0; 
}


Measured memory_bytes: 3536