akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
using Graph = vector<vector<int>>;
const int INT_INF = 1001001001;
//stoi(s) : string→int stoll(s) :string→longlong  int→string to_string(i)
const double PI = acos(-1.0);
//小数点の表し方 cout << fixed << setprecision(5);

int main(){
    string t;
    cin >> t;
    int n = t.size();
    if(t[0] == '?'){
        t[0] = 'D';
    }
    for(int i=1;i<n;i++){
        if(t[i] == '?'){
            t[i] = 'D';
        }
    }
    cout << t << endl;
}

Measured memory_bytes: 3752
x=[]
for i in range(5):
    x.append(int(input()))
k=int(input())
s="Yay!"
for i in range(5):
    for j in range(5-i-1):
        if abs(x[i+j+1]-x[i])>k:
            s=":("
            break
    if s==":(":
        break
print(s)


Measured memory_bytes: 3060
#include <cstdio>
#include <climits>
#include <cmath>
#include <iostream>
#define _for(i,n) for(int i = 0; i < n; i++)

using namespace std;



int main() {
  int n,k;
  string s;
  cin >> n >> s >> k;
  char kc = s[k-1];
  _for(i,n) {
    if (s[i]!=kc) {
      s[i] = '*';
    }
  }
  cout << s << endl;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
 
using namespace std;
long long mod=1e9+7;
long long INF=1e7;
double EPS = 1e-12;
const long long lim = 2e5+100;
typedef long long int lld;
typedef long long ll;

#define rep(i,a,n) for(long long int i = (a); i <= (n); ++i)
#define mset(a, v) memset(a, v, sizeof(a))
#define Error(x...) { cout << "(" << #x << ")" << " = ( "; printIt(x); }
template <typename T1> void printIt(T1 t1) { cout << t1 << " )" << endl; }
template <typename T1, typename... T2>
void printIt(T1 t1, T2... t2) { cout << t1 << " , "; printIt(t2...); }
 
 
#define popcount __builtin_popcountll
 
ll powP(ll x, ll y) {
    ll ans = 1, po = x % mod;
    while(y > 0) {
        if(y & 1) ans = ans * po % mod;
        y >>= 1; po = po * po % mod;
    }
    return ans;
}


vector<ll> Ans, Adj[lim];
ll Array[lim], C[lim],dp[600][600];
pair<ll,ll> P[lim];

ll dfs(ll node,ll par) {
    ll countA=1;
    for(auto i: Adj[node]) {
        if(i!=par) {
            ll val = dfs(i,node);
            countA+= val;
            Ans.push_back(val);
        }
    }
    return countA;
}

int main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

    #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
    
    lld T,i,p,j,l,e,r,b,c,k,m,q,a,d,w,x,y,u,v,z,t,curr,prev,sum=0,val,countA=0,indicator=0,pos,h,minA,maxA,type,n,ans=0,left,right;
    string A,B;
    cin>>A;
    for(auto i:A) {
        sum+=(i-'0');
    }

    sum%9 == 0 ? (cout<<"Yes"<<endl) : (cout<<"No"<<endl);

    return 0;
}
    


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

int A[200005];
long long pre[200005];

map<int, int> M;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);

    int N, K;
    cin >> N >> K;

    for(int i=1; i<=N; i++)
    {
        cin >> A[i];
        pre[i] = pre[i-1] + A[i];
    }

    for(int i=0; i<min(N+1, K); i++)
        M[(pre[i] - i + K) % K]++;
    
    long long ans = 0;

    for(auto it : M)
        ans += 1LL * it.second * (it.second - 1) / 2;
    
    for(int i=K; i<=N; i++)
    {
        M[((pre[i-K] - (i-K))%K + K) % K]--;
        ans += M[((pre[i] - i)%K + K) % K];
        M[((pre[i] - i)%K + K) % K]++;
    }

    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 12032
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <fstream>
#include <string>
#include <math.h>
#include <cstdlib>
#include <istream>
#include <sstream>
#include <cctype>
#define fore(i,x,y) for(long long i=x;i<y;i++)
typedef long long ll;
using namespace std;
int main()
{
	int A,B,C,D;
	cin>>A>>B>>C>>D;
	if(A*B>C*D){
		cout << A*B << endl;
	}
	else{
		cout << C*D << endl;
	}
}

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

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a.at(i);
  vector<bool> dp(k + 1);
  for (int i = 0; i <= k; i++) {
    for (int d : a) {
      if (i - d < 0) continue;
      if (dp.at(i - d) == false) dp.at(i) = true;
    }
  }
  if (dp.at(k)) {
    cout << "First" << endl;
  } else {
    cout << "Second" << endl;
  }
}


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

int main()
{

char a[110000];
scanf("%s",&a);
int flag=0;
int p=strlen(a);
for(int i=0;a[i];i++)
{
    if(a[i]=='d')
    {
        if(a[i+1]=='r'&&a[i+2]=='e'&&a[i+3]=='a'&&a[i+4]=='m')
        {
            if(a[i+5]=='d')
            {
                i=i+4;
                 continue;
            }
            else if(a[i+5]=='e'&&a[i+6]=='r'&&a[i+7]=='d')
            {
                i=i+6;
                 continue;
            }
            else if(a[i+5]=='e'&&a[i+6]=='r'&&i+7==p)
            {
                i=i+6;
                 continue;
            }
            else if(a[i+5]=='e'&&a[i+6]=='r'&&a[i+7]=='a')
            {
                i=i+4;
                 continue;
            }

            else if(a[i+5]=='e'&&a[i+6]=='r'&&a[i+7]=='e')
            {
                i=i+6;
                 continue;
            }

            else if(i+5==p)
            {
                i=i+4;
                 continue;
            }
            else
            {
                flag=1;
                break;
            }
        }
        else
        {
            flag=1;
            break;
        }
    }
    if(a[i]=='e')
    {
        if(a[i+1]=='r'&&a[i+2]=='a'&&a[i+3]=='s'&&a[i+4]=='e')
        {
            if(a[i+5]=='d')
            {
               i=i+4;
               continue;
            }
            else if(a[i+5]=='r')
            {
                i=i+5;
                 continue;

            }
            else if(a[i+5]=='e')
            {
                i=i+4;
                 continue;
            }
             else if(i+5==p)
            {
                i=i+4;
                 continue;
            }
            else
            {
                flag=1;
                break;
            }
        }
        else
        {
            flag=1;
            break;
        }
    }
}
if(flag==1)
{
    printf("NO\n");
}
else
{
    printf("YES\n");
}
    return 0;
}
//dreamerasedreamereraser


Measured memory_bytes: 384
strs = input()
h = 0
heights = [0]
max_h = 0
k = []
sum = 0
for i, s in enumerate(strs, 1):
    if s=='\\':
        h -= 1
        heights.append(h)
    elif s=='/':
        h += 1
        heights.append(h)
        if h>max_h:
          max_h = h
          continue
        t = -2
        while t+i+1>=0:
            if heights[t]==h:
                sum += (-t-3)+1
                tmp = (-t-3)+1
                if len(k)>0:
                  c = len(k)
                  for ts, te, tm in k[::-1]:
                    c -= 1
                    if t+i+1<ts and te<i:
                        k.pop(c)
                        tmp += tm
                k.append([t+i+1, i, tmp])
                break
            else:
                t -= 1
                continue
    else:
        heights.append(h)
        continue
print(sum)
ans = [str(k[-1]) for k in k]
print(len(ans), *ans)


Measured memory_bytes: 7136
using System;
using System.Collections.Generic;
using System.Diagnostics.Tracing;
using System.Linq;
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        var N = int.Parse(ReadLine());
        var S = ReadLine();

        var RGBList = new List<int>[3] { new List<int>(), new List<int>(),new List<int>() };
        var RGB2Int = new Dictionary<char, int> { { 'R', 0 }, { 'G', 1 }, { 'B', 2 } };
        var RGB2Char = "RGB";

        for (int i = 0; i < N; i++)
        {
            RGBList[RGB2Int[S[i]]].Add(i);
        }

        var RGBCount = new int[3, N];

        for (int i = N - 1; i >= 0; i--)
        {
            for (int j = 0; j < 3; j++)
            {
                if (S[i] == RGB2Char[j])
                {
                    if ((i + 1) < N)
                    {
                        RGBCount[j, i] = RGBCount[j, i + 1] + 1;
                    }
                    else
                    {
                        RGBCount[j, i] = 1;
                    }
                }
                else
                {
                    if ((i + 1) < N)
                    {
                        RGBCount[j, i] = RGBCount[j, i + 1];
                    }
                }
            }
        }

        var ans = 0L;
        var set = new (int, int, int)[6] { (0, 1, 2), (0, 2, 1), (1, 2, 0), (1, 0, 2), (2, 0, 1), (2, 1, 0), };

        foreach (var (C0, C1, C2) in set)
        {
            for (int i = 0; i < RGBList[C0].Count; i++)
            {
                for (int j = 0; j < RGBList[C1].Count; j++)
                {
                    var (C0I, C1I) = (RGBList[C0][i], RGBList[C1][j]);
                    if (C1I <= C0I)
                        continue;

                    ans += RGBCount[C2, C1I];//RGBList[C2].Where(x => C1I < x).Count();

                    var C2I = (C1I - C0I) + C1I;
                    if (C2I < N && S[C2I] == RGB2Char[C2])
                        ans--;
                }
            }
        }

        WriteLine(ans);
    }
}


Measured memory_bytes: 27964
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		for(int i=0; i<3; i++) {
			String str = sc.next();
			String STR = str.toUpperCase();
			char moji = STR.charAt(0);
			System.out.print(moji);
		}
	}
}

Measured memory_bytes: 24916
# AOJ ITP2_7_D: Multi-Set
# Python3 2018.6.24 bal4u

from bisect import bisect_left, bisect_right, insort_left
dict = {}
keytbl = []
cnt = 0
q = int(input())
for i in range(q):
	a = list(input().split())
	ki = int(a[1])
	if a[0] == '0':
		if ki not in dict:
			dict[ki] = 1
			insort_left(keytbl, ki)
		else: dict[ki] += 1
		cnt += 1
		print(cnt)
	elif a[0] == '1': print(dict[ki] if ki in dict else 0)
	elif a[0] == '2':
		if ki in dict:
			cnt -= dict[ki]
			dict[ki] = 0
	else:
		L = bisect_left (keytbl, int(a[1]))
		R = bisect_right(keytbl, int(a[2]), L)
		for j in range(L, R):
			for k in range(dict[keytbl[j]]): print(keytbl[j])


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

int main (){
  int a,b,c,d,e,f,g;
  cin >> a >> b >> c;
  d = a+b;
  e = a-b;
  f = a*b;
  if( d >= e && d >= f)
    g = d;
  if( e >= d && e >= f)
    g = e;
  if ( f >= d && f >= e)
    g = f;
  cout << g;
  return 0;
}

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

int main(int argc, char const *argv[])
{
    int A, B, M;
    cin >> A >> B >> M;

    vector<int> fridge_A(A);
    vector<int> fridge_B(B);
    for (int i = 0; i < A; i++)
    {
        cin >> fridge_A.at(i);
    }
    for (int i = 0; i < B; i++)
    {
        cin >> fridge_B.at(i);
    }

    int x, y;
    int discount;
    vector<int> sum(M);
    for (int i = 0; i < M; i++)
    {
        cin >> x >> y >> discount;
        sum.at(i) = fridge_A.at(x - 1) + fridge_B.at(y - 1) - discount;
    }

    sort(sum.begin(), sum.end());

    sort(fridge_A.begin(), fridge_A.end());
    sort(fridge_B.begin(), fridge_B.end());
    int sum_without = fridge_A.at(0) + fridge_B.at(0);
    cout << min(sum.at(0), sum_without) << endl;
    return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 30;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, z, w;
    cin >> n >> z >> w;
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    int x[n - 1], y[n - 1], tmp;
    for (int i = n - 2; i >= 0; i--) {
        tmp = INF;
        for (int j = i + 1; j < n - 1; j++) {
            tmp = min(tmp, y[j]);
        }
        x[i] = min(tmp, abs(a[i] - a[n - 1]));
        tmp = 0;
        for (int j = i + 1; j < n - 1; j++) {
            tmp = max(tmp, x[j]);
        }
        y[i] = max(tmp, abs(a[n - 1] - a[i]));
    }
    int res = 0;
    for (int i = 0; i < n - 1; i++) {
        res = max(res, x[i]);
    }
    res = max(res, abs(a[n - 1] - w));
    cout << res << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
#include <cstdarg>
#include <sys/time.h>
#include <fstream>
//#include "cout.h"

using namespace std;

#define SZ(x) ((int)x.size())
#define MSET(x,a) memset(x, a, (int)sizeof(x))
#define PB push_back
#define VI vector < int >
#define PII pair < int, int >
#define LL long long
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(), (v).end()
#define FIT(it,v) for (__typeof((v).begin()) it = (v).begin(); it != (v).end(); it++)
#define OUT(A) cout << #A << " = "<< (A) << endl
#define OUT2(A, B) cout << "(" << #A << ", " << #B << ") = (" << (A) << ", "<< (B) << ")" << endl
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }

#define present(c, e) ((c).find((e)) != (c).end())
#define cpresent(c, e) (find(ALL(c), (e)) != (c).end())

const LL MOD = 1000000007;

long long modPow(long long x, long long y){
    long long r=1, a=x%MOD;
    while(y > 0){
        if((y&1) == 1) r = (r*a) % MOD;
        a = (a*a) % MOD;
        y /= 2;
    }
    return r;
}

LL dp[110][10];
LL dp2[10];
int h, w, k;

void init() {

}

void input() {
  cin >> h >> w >> k;
}

void solve() {
  dp2[0] = 1;
  dp2[1] = 1;
  dp2[2] = 2;
  FOR(i, 3, 10) {
    dp2[i] = (dp2[i-1] + dp2[i-2]) % MOD;
  }

  dp[0][1] = 1;
  FOR(i, 1, h+1) FOR(j, 1, w+1) {
    dp[i][j] = (dp[i][j] + dp[i-1][j] * dp2[j-1] * dp2[w-j]) % MOD;
    if (j >= 2) {
      dp[i][j] = (dp[i][j] + dp[i-1][j-1] * dp2[j-2] * dp2[w-j]) % MOD;
    }
    if (j <= w-1) {
      dp[i][j] = (dp[i][j] + dp[i-1][j+1] * dp2[j-1] * dp2[w-1-j]) % MOD;
    }
  }
  cout << dp[h][k] << endl;;
}

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


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
    unsigned long long int X, Gohyaku = 0, amari = 0;
    unsigned long long int Goen = 0, answer = 0;
    scanf("%llu", &X);

    Gohyaku = X/500;
    amari = X%500;
    Goen = amari/5;

    answer = Gohyaku * 1000 + Goen * 5;

    printf("%llu", answer);
    
    return 0;
}

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

class Siritori
{
    static void Main()
    {
        int count = int.Parse(Console.ReadLine());
        string[] words = new string[count];
        for(int i=0;i<count;i++)
            words[i] = Console.ReadLine();

        //check contains
        foreach(string str in words)
        {
            int contains=0;
            foreach(string str2 in words)
                if(str == str2)
                    contains++;
            if(contains > 1)
            {
                Console.WriteLine("No");
                return;
            }
        }

        //check word connection
        for(int i = 0;i<count-1;i++)
        {
            if(words[i][words[i].Length -1] != words[i+1][0])
            {
                Console.WriteLine("No");
              	return;
            }
        }

        Console.WriteLine("Yes");
    }
}


Measured memory_bytes: 13140
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <map>
#include <numeric>
#include <algorithm>
#include <stdio.h>

int main(void){
  int x;
  std::cin >> x;
  if(400<=x&&599>=x){
    std::cout << 8;
  }else if(600<=x&&799>=x){    
    std::cout << 7;
  }else if(800<=x&&999>=x){    
    std::cout << 6;
  }else if(1000<=x&&1199>=x){    
    std::cout << 5;
  }else if(1200<=x&&1399>=x){    
    std::cout << 4;
  }else if(1400<=x&&1599>=x){    
    std::cout << 3;
  }else if(1600<=x&&1799>=x){    
    std::cout << 2;
  }else if(1800<=x&&1999>=x){    
    std::cout << 1;
  }
  return 0;
}

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

int main(){
    int n,k,j,t,sc;
    scanf("%d %d", &n, &k);
    int h[n];
    int a[n];
    scanf("%d %d", &h[0], &h[1]);
    a[0] = 0; a[1] = abs(h[1] - h[0]);
    for(int i = 2; i < n; i++){
        scanf("%d", &h[i]);
        j = i-2;
        t = k-1;
        sc = a[i-1] + abs(h[i] - h[i-1]);
        while(j > -1 && t > 0){
            sc = min(sc, a[j] + abs(h[i] - h[j]));
            j -= 1;
            t -= 1;
        }
        a[i] = sc;
    }
    printf("%d", a[n-1]);
    return 0;
}


Measured memory_bytes: 1024
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "vector"
#include "string"
#include "map"
#include "algorithm"
#include "functional"
#include "set"

using namespace std;

const long long int MOD = 1000000007;

int N, M, K, H, W, L, R;

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

	cin >> N;
	cout << (N / 111 + !!(N % 111)) * 111 << endl;
	return 0;
}


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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); 	
	
	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	int dx = x2 - x1, dy = y2 - y1;
	int x3 = x2 - dy, y3 = y2 + dx;
	int x4 = x1 - dy, y4 = y1 + dx;
	cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;
	return 0;
}



Measured memory_bytes: 256
def main():
    k = int(input().strip())
    if k % 2 == 0 or k % 5 == 0:
        print(-1)
        return
    x = 7 % k
    for n in range(1, k + 1):
        if x == 0:
            print(n)
            return
        x = (10 * x + 7) % k

    print(-1)
    return


if __name__ == "__main__":
    main()


Measured memory_bytes: 62072
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
#define drep(i,cc,n) for(int i=cc;i>=n;--i)
typedef long long ll;
using namespace std;
int main(){
    int n;
    cin>>n;
    int a[n];
    rep(i,0,n-1) cin>>a[i];
    bool flag = false;
    sort(a,a+n);
    rep(i,0,n-2){
        if(a[i]==a[i+1]) flag = true;
    }
    if(flag) cout<<"NO"<<endl;
    else cout<<"YES"<<endl;
    return 0;
}

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

int main(){
	string str;
	vector<string> pr;
	int n;
	cin>>str;
	cin>>n;;
	for(int i=0; i<n; i++){
		string s;
		int a,b;
		cin>>s>>a>>b;
		if(s=="replace"){
			string t;
			cin>>t;
			str.replace(a,b-a+1,t);
		}else if(s=="reverse"){
			string sub=str.substr(a,b-a+1);
			for(int j=0; j<sub.size(); j++) str[a+j]=sub[sub.size()-1-j];
		}else if(s=="print"){
			pr.push_back(str.substr(a,b-a+1));
		}
	}
	for(int i=0; i<pr.size(); i++){
		cout<<pr[i]<<endl;
	}
}


Measured memory_bytes: 3224
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stdio.h>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include<bits/stdc++.h>
#include <utility>

#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,a,b) for(int i = (a); (b) <= i; i--)
#define REP(i,n) for(int i = 0; i < (n); i++)
#define RREP(i,n) for(int i = n; n <= i; i--)
#define ABS(a) ((a < 0) ? ((-1)*(a)) : (a))
#define elif else if
#define MOD 1000000007
#define INF (1<<29)

using namespace std;
using ll = long long;
map <int ,int> mpa,mpb;
typedef pair<ll, ll> P;
priority_queue<P, vector<P>, greater<P>> pque;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N;
  cin >> N;
  ll ans=111;
  while(ans<1000){
    if(ans>=N){
      cout << ans << endl;
      return 0;
    }else{
      ans+=111;
    }
  }
  return 0;
}


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

using namespace std;


using int64 = long long;
const int mod = 1e9 + 7;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
  os << p.first << " " << p.second;
  return os;
}

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

template< typename F >
struct FixPoint : F {
  FixPoint(F &&f) : F(forward< F >(f)) {}

  template< typename... Args >
  decltype(auto) operator()(Args &&... args) const {
    return F::operator()(*this, forward< Args >(args)...);
  }
};

template< typename F >
inline decltype(auto) MFP(F &&f) {
  return FixPoint< F >{forward< F >(f)};
}


int main() {
  int N;
  cin >> N;
  vector< int > A(N);
  cin >> A;
  // もっともむずかしい
  for(int i = 0; i < N; i++) {
    if(A[i] % 2) continue;
    if(A[i] % 3 == 0 || A[i] % 5 == 0) {
      continue;
    }
    cout << "DENIED\n";
    exit(0);
  }
  cout << "APPROVED\n";
}


Measured memory_bytes: 256
m,d = map(int,input().split())
result = 0
if d <= 21:
    print(0)
    exit()
else:
    for month in range(4,m+1):
        for day in range(22,d+1):
            d10 = int(str(day)[0])
            d1 = int(str(day)[1])
            if d1 >= 2 and d10 >= 2:
                if month == d10*d1:
                    result += 1
    print(result)

Measured memory_bytes: 3060
def main():
  N = str(input())

  if N[-1] == '2' or N[-1] == '4' or N[-1] == '5' or N[-1] == '7' or N[-1] == '9':
    print('hon')
  elif N[-1] == '0' or N[-1] == '1' or N[-1] == '6' or N[-1] == '8':
    print('pon') 
  else:
    print('bon')

if __name__ == '__main__':
  main()

Measured memory_bytes: 9116
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 1e5+5;

int main(){
	ll x; cin >> x;
	ll ans = x / 500 * 1000;
	x %= 500;
	ans += x / 5 * 5;
	cout << ans << endl;
}

Measured memory_bytes: 256
use std::collections::HashMap;
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
fn main(){
    let n:i64 = read();
    let len = n /2;
    let an = read_vec::<i64>();
    if an.iter().all(|&x| x==an[0]){
        println!("{}",len);
        return;
    }
    let even:Vec<_> = an.iter().enumerate().filter(|&(i,v)| i % 2 == 0).map(|(k,v)|v).collect();
    let odd:Vec<_> =  an.iter().enumerate().filter(|&(i,v)| i % 2 != 0).map(|(k,v)|v).collect();
    let mut even_map:Vec<(_,_)> = even.iter().fold(HashMap::new(), |mut map, x| {
            let y = map.get(&x).map(|i| i + 1).unwrap_or(1);
            map.insert(x, y);
            map
        }).into_iter()
        .collect();
    even_map.sort_by_key(|x| x.1);
    let mut odd_map:Vec<(_,_)> = odd.iter().fold(HashMap::new(), |mut map, x| {
            let y = map.get(&x).map(|i| i + 1).unwrap_or(1);
            map.insert(x, y);
            map
        }).into_iter()
        .collect();
    odd_map.sort_by_key(|x| x.1);
    let even1 = even_map.last().unwrap();
    let odd1 = odd_map.last().unwrap();
    let even2 = if even_map.len() == 1 {
        0
    } else {
        even_map[(even_map.len() -2 )as usize].1
    };
    let odd2 = if odd_map.len() == 1 {
        0
    } else {
        odd_map[(odd_map.len() -2) as usize].1
    };

    let ans = if odd1.0 == even1.0 {
        let first = n - odd1.1 - even2;
        let second = n -even1.1 - odd2;
        std::cmp::min(first,second)
    } else{
        n - odd1.1 - even1.1
    };
    println!("{}",ans);
}

Measured memory_bytes: 12148
io = STDIN
k=[]
N,m=io.gets.split.map(&:to_i)
sw=m.times.map do 
  ar=io.gets.split.map(&:to_i)
  k << ar.shift
  ar
end
par=io.gets.split.map(&:to_i)
sws=sw.flatten.uniq.sort
$sws=[]
def gen(sw)
  if sw.size==N
    $sws << sw
    return
  end
  gen(sw+[true])
  gen(sw+[false])
end
def hantei(pattern,sw,par)
  bool = sw.map{|i|pattern[i-1]}.count{|e|e==true}%2 == par
  bool
end
gen([])
ans=0
$sws.map do |pattern|
  ar=sw.size.times.map do |i|
    hantei(pattern,sw[i],par[i])
  end
  ans+=1 if ar.all?
end
p ans


Measured memory_bytes: 3068
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+100;
ll a[N],d[N];

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int ans=0;
    int l,r,d;
    cin>>l>>r>>d;
    for(int i=1;i*d<=r;i++){
        if(i*d>=l&&i*d<=r) ans++;
    }
    cout<<ans<<endl;
    return 0;
}


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

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define int long long
#define pb push_back
#define pii pair<int,int>
#define fr(i,n) for(int i=0;i<n;i++)
#define F first
#define S second
#define nl '\n'
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int32_t main()
{   fastio;

    char c;
    cin>>c;
    if(c <= 'z' && c >= 'a') {
        cout<<'a';
    }
    else {
        cout<<'A';
    }
}

Measured memory_bytes: 3604
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

////////////////*My library*////////////////////////
#define rep_to(a,i,n) for(i=a;i<n;i++)
#define rep(i,n) for(i=0;i<n;i++)
#define rep_r(i,n) for(i=n-1;i>=0;i--)
#define debug_i(x) printf("x:%d\n",x)
#define debug_f(x) printf("x:%f\n",x)
#define debug_s(str) printf("str:%s\n",str)
#define debug_c(c) printf("c:%c\n",c)
#define s_i1(x) scanf("%d",&x)
#define s_i2(x,y) scanf("%d %d",&x,&y)
#define s_i3(x,y,z) scanf("%d %d %d",&x,&y,&z)
////////////////////////////////////////////////////

////////////////////////
/*prime()*/
/*primecount()*/
/*sort()*/
///////////////////////

int main()
{
	int a,b;
	while(s_i2(a,b)!=EOF){
	printf("%d\n", a+b);}
	return 0;
}

Measured memory_bytes: 1028
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll mod = 1e9 + 7;
const ll b1 = 1009, b2 = 10007;

ll Pow(ll a, ll b) {
	ll res = 1; a %= mod;
	while (b) {
		if (b & 1) {
			res = (res * a) % mod;
		}
		a = (a * a) % mod;
		b >>= 1;
	}
	return res;
}

class RollingHash {
	int N;
	string s;
	vector<ll> r1, r2, h1, h2, rh1, rh2;
public:
	RollingHash(const string& s_)
		: N((int)s_.size()), s(s_), r1(N + 1), r2(N + 1), h1(N + 1), h2(N + 1), rh1(N + 1), rh2(N + 1) {
		r1[0] = r2[0] = 1;
		for (int i = 1; i <= N; i++) r1[i] = r1[i - 1] * b1 % mod;
		for (int i = 1; i <= N; i++) r2[i] = r2[i - 1] * b2 % mod;

		h1[0] = h2[0] = 1;
		for (int i = 1; i <= N; i++) h1[i] = (h1[i - 1] * b1 + s[i - 1]) % mod;
		for (int i = 1; i <= N; i++) h2[i] = (h2[i - 1] * b2 + s[i - 1]) % mod;
	}
	P get(int l, int r) {
		return P((h1[r + 1] - h1[l] * r1[r - l + 1] % mod + mod) % mod, (h2[r + 1] - h2[l] * r2[r - l + 1] % mod + mod) % mod);
	}
};

int main()
{
	int n, m, l = 0, r = 0;
	string S, q;
	cin >> n >> m;
	cin >> S;
	RollingHash rh(S);
	vector<P> res;
	while (m--) {
		cin >> q;
		if (q == "R++") {
			r++;
		}
		if (q == "R--") {
			r--;
		}
		if (q == "L++") {
			l++;
		}
		if (q == "L--") {
			l--;
		}
		res.push_back(rh.get(l, r));
	}
	sort(res.begin(), res.end());
	res.erase(unique(res.begin(), res.end()), res.end());
	cout << res.size() << endl;
	return 0;
}

Measured memory_bytes: 26100
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define maxn 100
#define mod 998244353
using namespace std;




int main() {
    int a, b;
    cin >> a >> b;
    for(int i=1;i<=100000;i++){
        int x, y;
        x = (i * 8) / 100;
        y = (i * 10) / 100;
        if(x == a && y == b){
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ALL(c) begin(c), end(c)
using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e6+6;

template<typename T>
struct rmq {
	vector<T> t;
	size_t d;
	
	rmq(size_t sz, const T &val = T()): t(sz*2,val), d(sz) {}
	rmq(const vector<T> &vals){
		d = size(vals);
		t.resize(d*2);
		copy(ALL(vals), begin(t)+d);
		for(int i=d-1;i>0;--i) t[i] = max(t[i*2], t[i*2+1]);
	}
		
	void set_value(size_t i, const T& val){
		for(t[i+=d]=val; i>1; i>>=1) t[i>>1] = max(t[i], t[i^1]);
	}
		
	T operator()(size_t l, size_t r){
		T res = t[l+=d];
		for(++l,r+=d; l<r; l>>=1,r>>=1){
			if(l&1) res = max(res, t[l]), ++l;
			if(r&1) --r, res = max(res, t[r]);
		}
		return res;
	}
};

int main(){
	//freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);//cout.precision(12);cout<<fixed;
	
	int W,H,n;
	
	cin>>H>>W>>n;
	
	vector<pair<int,int>> p(n);
	vector<int> cnt(W);
	vector<vector<int>> q(H);
	for(auto &[y,x] : p){
		cin>>y>>x;
		--x; --y;
		++cnt[x];
		q[y].push_back(x);
	}
	
	rmq<int> f(cnt);
	
	int ans = 0;
	for(int y=0;y<H;++y){
		int cy = size(q[y]);
		for(int x : q[y]){
			int cx = cnt[x];
			ans = max(ans, cx+cy-1);
			f.set_value(x,0);
		}
		ans = max(ans, cy + f(0,W));
		for(int x : q[y]) f.set_value(x,cnt[x]);
	}
	
	cout<<ans<<endl;
	
	
	
	
	return 0;
}


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

using namespace std;
int main() {
    int len;
    double sum = 0;
    cin >> len;
    vector <double>x(len);
    vector <string>u(len);
    for(int i = 0; i < len; i++){
        cin >> x[i] >> u[i];
        if (u[i] == "BTC") {
            sum += x[i] * 380000;
        } else {
            sum += x[i];
        }
    }

    cout << sum << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
    char str[5];
    int num=0;
    int i;
    
    scanf("%s",str);
    
    for(i=0; str[i]!='\0'; i++){
        if(str[i] == '2'){
            num++;
        }
    }
    
    printf("%d\n",num);
    return 0;
    
    
}


Measured memory_bytes: 128
// Template {{{
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long LL;

#ifdef LOCAL
#include "contest.h"
#else
#define dump(x) 
#endif

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
inline bool valid(int x, int w) { return 0 <= x && x < w; }

void iostream_init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.setf(ios::fixed);
    cout.precision(12);
}
//}}}

int main(){
    iostream_init();
    int N;
    cin >> N;
    vector<int> A(1 << N);
    REP(i, 1<<N) cin >> A[i];
    REP(_, N) {
        vector<int> NA;
        for(int i = 0; i < A.size(); i += 2) {
            int x = A[i];
            int y = A[i+1];
            int z;
            if(x == y) {
                z = x;
            } else {
                z = max(x, y) - min(x, y);
            }
            NA.push_back(z);
        }
        swap(A, NA);
    }
    cout << A[0] << endl;
    return 0;
}



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


int main() {
    int cost = 0;
    int n,m,c; cin >> n >> m >> c;
    vector<int> b;
    for (int i = 0; i < m; i++) {
        int x; cin >> x;
        b.push_back(x);
    }
    int count = 0;
    for (int i = 0; i < n; i++) {
        int tmp = c;
        for (int j = 0; j < m; j++) {
            int y; cin >> y;
            tmp += y * b[j];
        }
        if (tmp > 0) {
            count++;
        }
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <utility>
#include <fstream>
//#include <random>
#include <map>
//#include <unordered_map>
#include <cstdlib>
#include <functional>
#include <time.h>
//#include <chrono>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <limits>
#include <numeric>
//#include <type_traits>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define INF 1000000001
#define MOD 1000000007
#define SORT(s) sort(s.begin(), s.end());
#define REVERSE(s) reverse(s.begin(), s.end());
#define SUM(s) accumulate(s.begin(), s.end(), 0LL);
#define P pair<int,int>
#define mp make_pair
#define valid(x,y,h,w) (0<=x&&x<h&&0<=y&&y<w)
//#define int ll
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int ndx[8] = { 0,1,0,-1, 1,1,-1,-1 };
int ndy[8] = { 1,0,-1,0, 1,-1,-1,1 };
double pi = 3.141592653589793;
using namespace std;
int POW(int x, int y) { return int(pow(double(x), double(y))); }
double log(double a, double b) { return log(b) / log(a); }

void solve1();
int score1();
int change(int, int, int);
vector<int> changeT(vector<int>);

int ti;
int D;
int sumC;
int k = 26;
int score;
vector<int> c(k), t, tz;
vector<vector<int>> s;

int main() {
	srand((unsigned)time(NULL));
	cin >> D;
	s.resize(D);

	rep(i, k) {
		cin >> c[i];
		sumC += c[i];
	}
	rep(i, D) {
		s[i].resize(k);
		rep(j, k) {
			cin >> s[i][j];
		}
	}
	t.resize(D);

	rep(i, D) {
		t[i] = rand() % 26;
	}
	score = score1();

	solve1();

	//cout << score << endl;
	//score = score1();
	//cout << score << endl;


	rep(i, D) {
		cout << t[i] + 1 << endl;
	}

}

void solve1() {

	ti = clock();
	int count = 0;

	while (1) {
		count++;
		double time = (double)(clock() - ti) / CLOCKS_PER_SEC;
		if (time > 1.9) {
			break;
		}

		int no = rand() % 15;
		int sz = score;
		tz = t;
		//vector<P> temp;
		rep(i, no) {
			int d = rand() % D;
			int q = rand() % k;
			sz = change(sz, d, q);
			//temp.push_back(mp(d, q));
		}

		if (sz > score) {
			score = sz;
			t = tz;
		}
		
	}

	//cout << count << endl;
}

vector<int> changeT(vector<int> t) {
	int no = rand() % 15;
	rep(i, no) {
		int d = rand() % D;
		int q = rand() % k;
		t[d] = q;
	}
	return t;
}

int score1() {
	//最後にコンテストが行われた日
	vector<int> last(k, -1);
	int ans = 0;

	rep(i, D) {
		ans += s[i][t[i]];
		last[t[i]] = i;
		rep(j, k) {
			ans -= c[j] * (i - last[j]);
		}
		//cout << ans << endl;
	}
	return ans;
}

int change(int score, int d, int q) {
	score += s[d][q] - s[d][tz[d]];
	int x = d + 1;
	while (x != D && tz[x] != q) {
		x++;
	}
	int y = d - 1;
	while (y >= 0 && tz[y] != q) {
		y--;
	}
	score += c[q] * (d - y) * (x - d);

	x = d + 1;
	while (x != D && tz[x] != tz[d]) {
		x++;
	}
	y = d - 1;
	while (y >= 0 && tz[y] != tz[d]) {
		y--;
	}
	score -= c[tz[d]] * (d - y) * (x - d);

	tz[d] = q;
	return score;
}

Measured memory_bytes: 3720
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define all(v) v.begin(), v.end()
using in = int64_t;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const double PI=3.14159265358979323846;
const int64_t waru = 1000000007;
const in INF=1<<30;
using vec = vector<vector<vector<vector<int>>>>;


int main(){
int n,m;
  cin>>n>>m;
  if(n==m ) cout<<"Yes";
  else cout<<"No";
}

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

int main(){
  int N;
  cin >> N;
  vector<int> As(N);
  for(int i = 0; i < N; i++){
    cin >> As.at(i);
  }
  sort(As.begin(), As.end());
  cout << abs(As.at(N-1) - As.at(0)) << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
#include<deque>
using namespace std;

using ll = long long;
const int INF = 1001001001;

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

typedef struct s_t {
  int x;
  int y;
} s_t;

int main()
{
  int h, w, d;
  cin >> h >> w >> d;
  vector<s_t> s(h*w + 1);

  rep(i, h) {
    rep(j, w) {
      int tmp;
      cin >> tmp;
      s[tmp].x = i+1;
      s[tmp].y = j+1;
    }
  }

  vector<ll> rui(h*w + 1, 0);
  //  for (int i = 1; i <= d; i++) {
  //    rui[i] = 0;
  //    for (int j = i+d; j <= h*w; j += d) {
  //      rui[j] = rui[j-d] + abs(s[j-d].x - s[j].x) + abs(s[j-d].y - s[j].y);
  //    }
  //  }
  for (int i = d+1; i <= h*w; i++) {
    rui[i] = rui[i-d] + abs(s[i].x - s[i-d].x) + abs(s[i].y - s[i-d].y);
  }

  int q;
  cin >> q;
  rep(i, q) {
    int l, r;
    cin >> l >> r;
    cout << rui[r] - rui[l] << endl;
  }
}


Measured memory_bytes: 2560
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(_i,_a,_n) for(int _i=_a;_i<=_n;++_i)
#define PER(_i,_a,_n) for(int _i=_n;_i>=_a;--_i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(_a) ({REP(_i,1,n) cout<<_a[_i]<<',';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



#ifdef __APPLE__
const int N = 1e2+50;
#else
const int N = 1e6+50;
#endif


int n;
ll a[N],sum[N];

int main() {
	scanf("%d", &n);
	REP(i,0,n) scanf("%lld", a+i);
	PER(i,0,n) sum[i]=sum[i+1]+a[i];
	if (n==0) {
		if (a[0]==1) puts("1");
		else puts("-1");
		return 0;
	}
	if (a[0]) return puts("-1"),0;
	ll ans = 1, now = 1;
	REP(i,1,n) {
		ll L = max(0ll,now-a[i]), R = min(sum[i],2*now)-a[i];
		if (L>R) return puts("-1"),0;
		ans += R+a[i];
		now = R;
	}
	printf("%lld\n", ans);
}









Measured memory_bytes: 5324
#include <iostream>

using namespace std;

int r_x1, r_y1, r_x2, r_y2;
int N, x, y, a;
int area;

int main() {
	cin >> r_x2 >> r_y2 >> N;
	area = r_x2 * r_y2;
	r_x1 = r_y1 = 0;
	for(int i = 0; i < N; i++) {
		cin >> x >> y >> a;
		if (a == 1) {
			r_x1 = max(r_x1, x);
		} else if (a == 2) {
			r_x2 = min(r_x2, x);
		} else if (a == 3) {
			r_y1 = max(r_y1, y);
		} else {
			r_y2 = min(r_y2, y);
		}
		if (r_x1 > r_x2 || r_y1 > r_y2) area = 0;
		if (area > 0) area = (r_x2 - r_x1) * (r_y2 - r_y1);
	}
	if (area < 0) area = 0;
	cout << area;
	return 0;
}

Measured memory_bytes: 256
x = int(input())
dp = [0]*(x+20)
for i in range(100,x+10):
    if 100<=i and i<=105:
        dp[i] = 1
        continue

    for j in range(0,6):
        if dp[i-100-j]==1:
            dp[i] = 1
            break
        else:
            continue
print(dp[x])

Measured memory_bytes: 40048
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

bool dfs(int n) {
  if(n==4 or n==7)
    return true;
  else if(n<4)
    return false;
  else if(n<7)
    return dfs(n-4);
  else
    return dfs(n-4) or dfs(n-7);
}

int main(void) {
  int n;
  cin>>n;
  if(dfs(n))
    cout<<"Yes";
  else
    cout<<"No";
  cout<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<algorithm>
#include<stdint.h>
#include<vector>
#include<string>
#include<time.h>
#include<random>
#include<bitset>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;


std::vector<ull> prime;

void initprime(ull MAX) {
    std::vector<bool> is_prime(MAX + 1);
    for (int i = 0; i <= MAX; ++i) is_prime[i] = true;
    for (int i = 2; i <= MAX; ++i) {
        if (is_prime[i]) {
            int loop = (MAX / i);
            for (int j = 2; j <= loop; ++j) {
                is_prime[i * j] = false;
            }
            prime.emplace_back(i);
        }
    }
}

//最大公約数
template<typename T>
constexpr T gcd(T a, T b)
{
	if (a % b == 0)
	{
		return(b);
	}
	else
	{
		return(gcd(b, a % b));
	}
}
ll gcd2(ll x, ll y) { return y ? gcd2(y, x % y) : x; }
//最小公倍数
template<typename T>
constexpr T lcm(T a, T b)
{
	return a * b / gcd(a, b);
}

vector<pair<ll, int>> factorize(ll n) {
    vector<pair<ll, int>> res;
    for (ll i = 2; i * i <= n; ++i) {
        if (n % i) continue;
        res.emplace_back(i, 0);
        while (n % i == 0) {
            n /= i;
            res.back().second++;
        }
    }
    if (n != 1) res.emplace_back(n, 1);
    return res;
}

ull p_cnt(ull g) {
    if (g == 1) return 1;
    ull rootg = floor(sqrt((double)g));
    ull p_cnt = 1;
    for (int i = 0; i < prime.size(); ++i) {
        if (g % prime[i] == 0) {
            ++p_cnt;
        }
    }
    if (p_cnt == 1) ++p_cnt;
    return p_cnt;
}

int main() {
    ll a, b;
    cin >> a >> b;
    ll g = gcd2(a, b);
    auto f = factorize(g);
    int ans = f.size() + 1;
    cout << ans << endl;
    return 0;

    initprime(100000);
    ll C = 100000000;
    for (ll i = 1; i <= C; ++i) {
        for (ll j = i; j <= C; ++j) {
            ull a = gcd(i,j);
            ull b = gcd2(i,j);
            if (a != b)
            {
                cout << i << "::" << a << "::" << b << endl;
            }
        }
    }
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#define all(a) a.begin(),a.end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef long double ld;
typedef complex<ld> com;
constexpr int inf = 1000000000;
constexpr ll INF = 1000000000000000000;
constexpr ld EPS = 1e-12;
constexpr ld PI = 3.141592653589793238;
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }

constexpr ll mod = 998244353;
constexpr ll modsize = 20000;
vector<ll> fac(modsize);
vector<ll> inv(modsize);
vector<ll> facinv(modsize);

void modcalc() {
	if (modsize == 0) abort();
	fac[0] = 1; fac[1] = 1; inv[1] = 1;
	facinv[0] = 1; facinv[1] = 1;
	for (ll i = 2; i < modsize; i++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = mod - inv[mod % i] * (mod / i) % mod;
		facinv[i] = facinv[i - 1] * inv[i] % mod;
	}
}

ll modinv(ll a) {
	if (a == 0) abort();
	ll b = mod, u = 1, v = 0;
	while (b) {
		ll t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= mod;
	if (u < 0) u += mod;
	return u;
}

ll modpow(ll a, ll b) {
	ll ans = 1;
	a %= mod;
	while (b) {
		if (b & 1) ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}

ll modcomb(ll n, ll k) {
	if (n < 0 || k < 0 || n < k) return 0;
	return fac[n] * facinv[k] % mod * facinv[n - k] % mod;
}

ll modperm(ll n, ll k) {
	if (n < 0 || k < 0 || n < k) return 0;
	return fac[n] * facinv[n - k] % mod;
}

ll modhom(ll n, ll k) {
	if (n < 0 || k < 0 || n == 0 && k > 0) return 0;
	if (n == 0 && k == 0) return 1;
	return fac[n + k - 1] * facinv[k] % mod * facinv[n - 1] % mod;
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);
	modcalc();

	ll k, n;
	cin >> k >> n;
	ll sum = modhom(k, n);
	for (ll i = 2; i <= 2 * k; i++) {
		ll ans = sum;
		ll b = min(i / 2, (2 * k - i) / 2 + 1);
		for (ll j = 1; j <= b; j++) {
			ll cnt = modhom(k, n - 2 * j)*modcomb(b, j) % mod;
			if (j & 1) cnt = mod - cnt;
			ans += cnt;
			if (ans >= mod) ans -= mod;
		}
		cout << ans << '\n';
	}
}

Measured memory_bytes: 768
# Vol0005.
import sys


def intinput():
    a = input().split()
    for i in range(len(a)):
        a[i] = int(a[i])
    return a

def get_gcd(x, y):
    if x < y: return get_gcd(y, x)
    # x >= yのときはx % yを計算してyとx % yの話にする。
    # ここでx % yのところが0ならばyが求める答えとなる。
    if y == 0: return x
    return get_gcd(y, x % y)

def main():
    data = []
    lines = sys.stdin.readlines()

    for line in lines:
        data.append(line.split())

    N = len(data)
    for i in range(N):
        a = int(data[i][0]); b = int(data[i][1])
        gcd = get_gcd(a, b)
        lcm = (a // gcd) * b
        print('%d %d' % (gcd, lcm))

if __name__ == "__main__":
    main()


Measured memory_bytes: 5596