akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int n;
long long dp[2001][2001], ans = 0;
vector<pair<int, int>> a;

int main() {
	cin >> n;
	for (int i = 0, m; i < n; i++) {
		cin >> m;
		a.emplace_back(m, i);
	}
	sort(a.begin(), a.end(), greater<pair<int, int>>());

	for (int i = 0; i < n; i++) { //既にi人並んでいる
		for (int j = 0; j < i + 1; j++) { //左からj人並んでいる
			//左側に追加
			dp[i + 1][j + 1] = max(dp[i + 1][j + 1],
					dp[i][j] + (long long) abs(j - a[i].second) * a[i].first);
			//右側に追加
			dp[i + 1][j] = max(dp[i + 1][j],
					dp[i][j]
							+ (long long) abs(n - i + j - 1 - a[i].second)
									* a[i].first);
		}
	}
	for (int i = 0; i <= n; i++) {
		ans = max(ans, dp[n][i]);
	}
	cout << ans << endl;
}


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

using namespace std;

#define mp make_pair
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define forlr(i, l, r) for (int i = int(l); i < int(r); i++)
#define repeat(n) for (int hjfjke = 0; hjfjke < int(n); hjfjke++)
#define all(c) c.begin(), c.end()
#define ll long long

int dp[100500];
int h[100500];

int32_t main() {
    std::iostream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, k;
    cin >> n >> k;
    forn(i, n)
        cin >> h[i];

    dp[0] = 0;
    forlr(i, 1, n) {
        dp[i] = 1e9 + 500;
        forlr(j, 1, k + 1)
            if (i >= j)
                dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]));
    }
    cout << dp[n - 1];

    return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using vi = vector<i64>;
using vvi = vector<vi>;
using ii = pair<i64, i64>;

int main() {
    int n;
    cin >> n;
    map<int, int> cnto, cnte;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        if (i % 2 == 1) {
            cnto[a]++;
        } else {
            cnte[a]++;
        }
    }
    vector<ii> oo, ee;
    for (auto& p: cnto) {
        oo.emplace_back(p.first, p.second);
    }
    for (auto& p: cnte) {
        ee.emplace_back(p.first, p.second);
    }
    sort(oo.begin(), oo.end(), [](ii a, ii b) {
        return a.second < b.second;
    });
    sort(ee.begin(), ee.end(), [](ii a, ii b) {
        return a.second < b.second;
    });

    int i, j;
    for (i = oo.size() - 1; i >= 0 && oo[i].second == oo.back().second; i--) {
        for (j = ee.size() - 1; j >= 0 && ee[j].second == ee.back().second; j--) {
            if (oo[i].first != ee[j].first) {
                cout << n - oo.back().second - ee.back().second << endl;
                return 0;
            }
        }
    }

    if (oo.size() == 1 && ee.size() == 1) {
        cout << n / 2 << endl;
        return 0;
    }

    if (oo.size() == 1) {
        cout << n / 2 - ee[ee.size() - 2].second << endl;
        return 0;
    }

    if (ee.size() == 1) {
        cout << n / 2 - oo[oo.size() - 2].second << endl;
        return 0;
    }


    cout << min({n - oo[oo.size() - 1].second - ee[ee.size() - 2].second, n - oo[oo.size() - 2].second - ee[ee.size() - 1].second}) << endl;
}

Measured memory_bytes: 7284
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
#include <iomanip>
#include <functional>
#include <queue>
#include <stack>
#include <cmath>
#define ll long long
#define INF 10000000000000000
#define MOD 998244353
using namespace std;

int main(){
    int N,K;
    cin >> N >> K;
    int A[N];
    int one;

    for(int i=0; i<N; i++){
        cin >> A[i];
    }
    
    int ans;
    for(int x=1; ; x++){
        if( (K-1)*(x-1)+2<=N && N<=(K-1)*x+1){
            ans=x;
            break;
        }
    }
    
    cout<<ans<<endl;
    
    
    return 0;
}


Measured memory_bytes: 640
n,x;main(i){
    for(scanf("%d",&n);i<=n;i++){
        x=i;
        if(x%3==0){
            printf(" %d",i);
            continue;
        }else if(x%10==3){
            printf(" %d",i);
            continue;
        }else{
            for(x/=10;x>0;x/=10){
                if(x%10==3){
                    printf(" %d",i);
                    break;
                }
            }
        }

    }
    puts("");
}

Measured memory_bytes: 1804
#include<bits/stdc++.h>
#define ford(i,a,b) for(int i=(a);i>=b;i--)
#define rep1(i,a,b) for(int i=(a);(i)<=(b);(i)++)
#define rep0(i,a,b) for(int i=(a);(i)<(b);(i)++)
#define ll long long
#define re return
#define mp map<int,int>
#define N 200005
#define pql priority_queue<ll>
#define all(v) (v).begin(),(v).end()
#define str stringstream
using namespace std;
int a[N],n;
bool pd=1;
int main() {
	cin>>n;
	rep0(i,0,n){
		cin>>a[i];
		if(a[i]%2==0){
			if(a[i]%3!=0&&a[i]%5!=0)
				pd=0;
		}
	}
	if(pd) cout<<"APPROVED";
	else cout<<"DENIED";
	re 0;
}


Measured memory_bytes: 256
import math

def gcd(a,b):
    while b !=0:
        a,b=b,a%b
    return a
    
def lcm(a,b):
    return (a*b)//gcd(a,b)    

A,B,C,D=map(int,input().split()[:4])

total=B-A+1

C_div=B//C-(A-1)//C
D_div=B//D-(A-1)//D

CD=lcm(C,D)

CD_div=B//CD-(A-1)//CD

print(total-C_div-D_div+CD_div)

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

#define ll long long
#define pb push_back
#define mp make_pair

bool comp(pair<int,int> a, pair<int,int> b) {
	return (a.first < b.first);
}

int main() {
	ios_base::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*/

	int n;
	int w;
	cin >> n >> w;
	vector <pair<int,int>> ele(n);
	for(int i=0,a,b;i<n;i++) {
		cin >> a >> b;
		ele[i] = mp(a,b);
	}
	sort(ele.begin(),ele.end(),comp);
	// for(int i=0;i<n;i++) {
	// 	cout << ele[i].first << " " << ele[i].second << '\n';
	// }

	ll dp[n+1][w+1];
	for(int i=0;i<=n;i++) {
		dp[i][0] = 0;
	}
	for(int i = 0;i<=w;i++) {
		dp[0][i] = 0;
	}
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=w;j++) {
			pair<int,int> obj = ele[i-1];
			int wt = obj.first;
			int val = obj.second;
			if(j >= wt) {
				dp[i][j] = max(dp[i-1][j],dp[i-1][j-wt] + val);
			}
			else {
				dp[i][j] = dp[i-1][j];
			}
		}
	}
	// for(int i=0;i<=n;i++) {
	// 	for(int j=0;j<=w;j++) {
	// 		cout << dp[i][j] << " ";
	// 	}
	// 	cout << '\n';
	// }
	cout << dp[n][w] << '\n';

}

Measured memory_bytes: 79104
s=input()
n=len(s)

K=int(input())

dp=[[[0] * 5 for _ in range(2)] for _ in range(n+1)]
dp[0][0][0]=1

for i in range(n):
    ni= int(s[i])

    for k in range(4):
            # smaller 1 -> 全部OK
            dp[i + 1][1][k + 1] += dp[i][1][k] * 9;  
            dp[i + 1][1][k] += dp[i][1][k];  

            # smaller 0,next smaller 1 -> nowより小さいのを全部
            # 次の桁からsmallerであるためにはN＜ni であることが必要で
            # Nは0より大きい必要がある。（0より小さいものがない＝確定しない
            if (ni > 0):
                dp[i + 1][1][k + 1] += dp[i][0][k] * (ni - 1)
                dp[i + 1][1][k] += dp[i][0][k]
                
            # smaller 0,next smaller 0 -> nowだけ
            if (ni > 0) :
                dp[i + 1][0][k + 1] = dp[i][0][k]
            else:
                dp[i + 1][0][k] = dp[i][0][k]

ans=dp[n][0][K] + dp[n][1][K]
print(ans)

Measured memory_bytes: 3064
#include<stdio.h>
#include<math.h>
 
int main(){
    int n;
    int Sn[1000];
    int sum=0;   // sum:??????°????????¨?
    int i;
    double ave;
    double a=0;   // a:??????£?????????
     
    while(1){
        scanf("%d",&n);
        if(n==0)   break;
        for(i=0;i<n;i++){
            scanf("%d",&Sn[i]);
            sum+=Sn[i];
        }
        ave=(double)sum/n;
     
        for(i=1;i<=n;i++){
            a+=pow(Sn[i-1]-ave,2);
        }
        a/=(double)n;
        printf("%.5lf\n",sqrt(a));
        sum=0;
        a=0;
    }
        return 0;
}

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

int main() {
  int64_t n;
  std::cin >> n;
  std::vector<int64_t> a(n);
  for (auto &i : a) {
    std::cin >> i;
  }
  int64_t sum = std::accumulate(a.cbegin(), a.cend(), 0);
  std::vector<std::vector<int64_t>> d(sum + 1, std::vector<int64_t>(2, 0));
  std::vector<std::vector<int64_t>> dd(sum + 1, std::vector<int64_t>(2, 0));
  d[0][0] = 1;
  dd[0][0] = 1;

  for (const auto i : a) {
    for (int64_t j = 0; j <= sum; j++) {
      if (d[j][0] != 0) {
        d[i + j][1] = d[j][0];
      }
      d[j][0] *= 2;
      d[j][0] %= 998244353;
      d[j][0] += d[j][1];
      d[j][0] %= 998244353;
      d[j][1] = 0;
      if (dd[j][0] != 0) {
        dd[i + j][1] += dd[j][0];
        dd[i + j][1] %= 998244353;
      }
    }
    for (int64_t j = 0; j <= sum; j++) {
      dd[j][0] += dd[j][1];
      dd[j][0] %= 998244353;
      dd[j][1] = 0;
    }
  }

  int64_t minus = 0;
  int64_t half = sum % 2 == 0 ? sum / 2 : sum / 2 + 1;

  for (int64_t j = half; j <= sum; j++) {
    minus += d[j][0];
    minus %= 998244353;
  }
  minus *= 3;
  minus %= 998244353;

  int64_t plus = 1;
  for (int64_t i = 0; i < n; i++) {
    plus *= 3;
    plus %= 998244353;
  }

  if (sum % 2 == 0) {
    plus += dd[half][0] * 3;
    plus %= 998244353;
  }

  if (plus < minus) {
    std::cout << plus - minus + 998244353 << std::endl;
  } else {
    std::cout << plus - minus << std::endl;
  }
  return 0;
}


Measured memory_bytes: 10112
import java.util.Scanner;

public class Main {

     static Scanner scanner;

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

         int N=gi();
         long M=gl();
         long[] a=new long[N];

         boolean flg=true;
         for (int i=0;i<N;i++) {
        	 a[i]=gi()/2;
         }
         int b=dt(a[0]);
         for (int i=1;i<N;i++) {
        	 if(dt(a[i])!=b) {
        		 flg=false;
        		 break;
        	 }
         }

         long ans=0;
         if(flg) {
        	 long kb=1;
             for (int i=0; i<N;i++) {
                 kb=kb*a[i] / uclid(kb,a[i]);
             }
             long tmp=Math.floorDiv(M, kb);
             if(tmp%2==0) {
            	 ans=tmp/2l;
             } else {
            	 ans=(tmp+1l)/2l;
             }
         }


         System.out.println(ans);
     }

     // ユークリッドの互除法
     public static long uclid(long m, long n) {
     	if (m<n) {
 			m^=n;
 			n^=m;
 			m^=n;
 		}

 		while(true) {
 			long t=m%n;
 			if (t==0) {
 				return n;
 			} else {
 				m=n;
 				n=t;
 			}
 		}
     }

     public static int dt(long n) {
    	 if(n==0)return 0;
    	 int ret=0;
    	 while((n&1)==0) {
    		 n=n>>1;
             ret++;
    	 }
    	 return ret;
     }

     // 文字列として入力を取得
     public static String gs() {
          return scanner.next();
     }

     // intとして入力を取得
     public static int gi() {
          return Integer.parseInt(scanner.next());
     }

     // longとして入力を取得
     public static long gl() {
          return Long.parseLong(scanner.next());
     }

     // doubleとして入力を取得
     public static double gd() {
          return Double.parseDouble(scanner.next());
     }
}

Measured memory_bytes: 60724
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long int;
const ll MOD = 1000000007;
const int LEN = 20;

// [l, r) の pos 文字目が v 以上
ll N, dp[55][55][30][30];
char dict[55][30];
char base = (char)('a' - 1);

ll solve(int l, int r, int pos, int v) {
    ll &res = dp[l][r][pos][v];
    if(res >= 0) return res;
    char target = (char)(base + v);

    if(l == r) return res = 1;
    if(v == 27) return res = 0;
    if(pos == LEN) return res = (r - l == 1);

    res = 0;
    for(int k=l; k<=r; k++) {
        if(k > l) {
            if(dict[k-1][pos] != target and dict[k-1][pos] != '?') break;
            if(v == 0 and dict[k-1][pos] == '?') break;
        }
        
        // [l, r) -> [l, k), [k, r)
        ll valL = solve(l, k, pos+1, 0);
        ll valR = solve(k, r, pos, v+1);
        (res += valL * valR) %= MOD;
    }
    return res;
}

int main() {
    cin >> N;
    for(int i=0; i<N; i++) {
        scanf("%s", dict[i]);
        for(int j=strlen(dict[i]); j<LEN; j++) dict[i][j] = base;
    }

    fill(dp[0][0][0], dp[N+1][0][0], -1);
    cout << solve(0, N, 0, 0) << endl;
    return 0;
}



Measured memory_bytes: 23016
n = int(input())
a = sorted(list(map(int,input().split())))
m = int(input())
b = sorted(list(map(int,input().split())))
now = 0
for i in range(len(b)) :
	while now < n and a[now] < b[i] :
		now += 1
	if a[now] != b[i] :
		print("NO")
		exit()
	now += 1
	if now == n and i != m - 1 :
		print("NO")
		exit()
print("YES")

Measured memory_bytes: 36820
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

g_cnt = 0
def main():
    N = I()
    dp = [[[[0 for _ in range(4)] for ____ in range(4)] for __ in range(4)] for ___ in range(N+1)]
    s2i = {
        'A': 0,
        'G': 1,
        'C': 2,
        'T': 3,
    }
    dp[0][3][3][3] = 1

    for i in range(0, N):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    for char in ['A', 'G', 'C', 'T']:
                        if char == 'G':
                            if k == s2i['A'] and l == s2i['C']:
                                continue
                        elif char == 'C':
                            if j == s2i['A'] and l == s2i['G']:
                                continue
                            if k == s2i['G'] and l == s2i['A']:
                                continue
                            if k == s2i['A'] and l == s2i['G']:
                                continue
                            if j == s2i['A'] and k == s2i['G']:
                                continue
                        else:
                            pass
                        dp[i+1][k][l][s2i[char]] += dp[i][j][k][l]
                        dp[i+1][k][l][s2i[char]] %= mod

    cnt = 0
    for j in range(4):
        for k in range(4):
            for l in range(4):
                cnt += (dp[N][j][k][l] % mod)
                cnt %= mod
    print(cnt)
main()



Measured memory_bytes: 5812
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

int main() {
  int n; cin >> n;
  int sum = 0;
  for (int i = 1; i <= n; i += 2) {
    int cnt = 0;
    for (int j = 1; j <= i; j ++) {
      if (i % j == 0) {
        cnt ++;
      }
    }
    if (cnt == 8) sum ++;
  }

  cout << sum << endl;
}


Measured memory_bytes: 256
import java.util.HashSet;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        HashSet<Character> hs = new HashSet();
        for (int i = 0; i < s.length(); i++) {
            hs.add(s.charAt(i));
        }
        String answer = "No";
        // AとBの2種類あればYes、1種類だけならNo
        if (hs.size() == 2) {
            answer = "Yes";
        }
        System.out.println(answer);
    }

}


Measured memory_bytes: 35612
#include<stdio.h>

int main(){
  int cards[4][13] = {0};
  int i, j, n;
  int num[52], marknum;
  char mark[52];
  
  scanf("%d", &n);
  
  for(i=0; i<n; i++){
    scanf(" %c %d", &mark[i], &num[i]);
    switch(mark[i]){
    case 'S':
      marknum = 0;
      break;
    case 'H':
      marknum = 1;
      break;
    case 'C':
      marknum = 2;
      break;
    case 'D':
      marknum = 3;
      break;
    }
    cards[marknum][num[i]-1] = 1;
  }
  

  
  for(i=0;i<4;i++){
    for(j=0;j<13;j++){
      switch(i){
      case 0:
        if(cards[0][j]==0){
          printf("S %d\n", j+1);
        }
        break;
      case 1:
        if(cards[1][j]==0){
          printf("H %d\n", j+1);
        }
        break;
      case 2:
        if(cards[2][j]==0){
          printf("C %d\n", j+1);
        }
        break;
      case 3:
        if(cards[3][j]==0){
          printf("D %d\n", j+1);
        }
        break;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 596
#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
#define MAX 10
using namespace std;

void Print(vector<int> &vec)
{
    printf("%d", vec[0]);
    for (unsigned i = 1; i < vec.size(); i++)
    {
        printf(" %d", vec[i]);
    }
    printf("\n");
}

int main()
{
    int n;
    scanf("%d", &n);

    vector<int> vec;
    for (int i = 1; i <= n; i++)
    {
        vec.push_back(i);
    }

    do
    {
        Print(vec);
    }while (next_permutation(vec.begin(), vec.end()));

    return 0;
}



Measured memory_bytes: 3264
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long int ll;

int main(){
	int N;
	cin >> N;
	vector<ll> A(N);
	ll x1 = 0;
	for(int i = 0; i < N; i++){
		cin >> A[i];
		if(i % 2 == 0) x1 += A[i];
		else x1 -= A[i];
	}
	vector<ll> res(N);
	res[0] = x1;
	A[0] -= x1 / 2;
	A[N - 1] -= x1 / 2;
	for(int i = 1; i < N; i++){
		res[i] = 2 * A[i - 1];
		A[i] -= res[i] / 2;
	}
	for(int i = 0; i < N; i++) cout << res[i] << (i == N - 1 ? '\n' : ' ');
	return 0;
}


Measured memory_bytes: 2816
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.close();

		int m = 1000000007;
		long a = power(10, n, m);
		long b = power(9, n, m);
		long c = power(8, n, m);
		long ans = a - b - b + c + m + m;
		ans %= m;
		System.out.println(ans);
	}

	static long power(long x, long n, int m) {
		if (n == 0) {
			return 1;
		}
		long val = power(x, n / 2, m);
		val = val * val % m;
		if (n % 2 == 1) {
			val = val * x % m;
		}
		return val;
	}
}


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


int main() {
  string S; cin >> S;
  long long K; cin >> K;

  int cnt = 0;
  for(int i=0; i<S.size(); i++){
    if(S[i]=='1') cnt ++;
    else break;
  }

  if(cnt==0) cout << S[0] << endl;
  else if(cnt >= K) cout << 1 << endl;
  else cout << S[cnt] << endl;

  return 0;
}



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

using namespace std;

bool wieksze(vector<int> a, vector<int> b)
{
    for(int i = 0;i<a.size();i++)
    {
        if(a[i]>b[i])return true;
        if(b[i]>a[i])return false;
    }
    return false;
}

int main()
{
    int n;
    cin>>n;
    vector<int> a;
    vector<int> b;
    a.assign(n,0);
    b.assign(n,0);
    for(int i = 0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i = 0;i<n;i++)
    {
        cin>>b[i];
    }
    if(!wieksze(a,b))
    {
        for(int i = 0;i<n;i++)swap(a[i],b[i]);
    }
    int ile = 0;
    while(wieksze(b,a)||wieksze(a,b))
    {
        next_permutation(b.begin(),b.end());
        ile++;
    }
    cout<<ile;
}


Measured memory_bytes: 256
import java.io.*;

class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		while(true){
			String lns[] = br.readLine().split(" ");
			int ln[] = parseInts(lns);
			if(ln[0]==0 && ln[1]==0) break;
			for(int x=0; x<ln[0] ;x++){
				for(int y=0; y<ln[1]; y++){
					if(y==ln[1]-1){
						System.out.println("#");
					}else if(y==0 || x==0 || x==ln[0]-1){
						System.out.print("#");
					}else{
						System.out.print("#");
					}
				}
			}
			System.out.println();
		}
	}
	static int[] parseInts(String[] s){
		int[] x = new int[s.length];
		for(int i=0;i<s.length;i++){
			x[i] = Integer.parseInt(s[i]);
		}
		return x;
	}
}

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

int main(){
 int N;
  cin >> N;
 int a[110];
  for (int i = 0; i < N ; i++) cin >> a[i];
  
  sort (a, a+N, greater<int>());
  
  int Alice = 0; 
  int Bob = 0;
  for (int i = 0; i < N ; i++){
    if (i % 2 == 0) {
      Alice = Alice + a[i];
    }else{
      Bob = Bob + a[i];
  }
  }
  cout << Alice - Bob << endl;
}

Measured memory_bytes: 256
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def longest_common_subsequence(S, T):
    """compute table dp satisfying: 
    dp[i,j] = LCS(S[:i], T[:j])"""
    LS, LT = len(S), len(T)
    dp = np.zeros((LS + 1, LT + 1), np.int32)
    for n in range(1, LS + 1):
        dp[n, 1:] = dp[n - 1, :-1] + (S[n - 1] == T)  # 左上から
        np.maximum(dp[n], dp[n - 1], out=dp[n])  # 上から
        np.maximum.accumulate(dp[n], out=dp[n])  # 左から
    return dp

def reconstruct_LCS(S, T, dp):
    tmp = []
    i, j = len(S), len(T)
    while i > 0 and j > 0:
        if S[i - 1] == T[j - 1]:
            i, j = i - 1, j - 1
            tmp.append(S[i])
        elif dp[i, j] == dp[i - 1, j]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(tmp))

S = np.array(list(readline().decode()), 'U1')[:-1]
T = np.array(list(readline().decode()), 'U1')[:-1]

dp = longest_common_subsequence(S, T)

print(reconstruct_LCS(S, T, dp))

Measured memory_bytes: 61968
#include<bits/stdc++.h>
using namespace std;
main(){
int N;
cin>>N;
int p=N+1;
double  P[p];
for(int i=1;i<=N;i++){cin>>P[i];}

double dp[N+1][N+1];
for(int i=0;i<=N;i++)dp[i][0]=0;
dp[0][0]=1;
for(int i=1;i<=N;i++)dp[0][i]=dp[0][i-1]*(1-P[i]);

for(int i=1;i<=N;i++)for(int j=1;j<=N;j++){
dp[i][j]=dp[i-1][j-1]*(P[j])+dp[i][j-1]*(1-P[j]);
}

long double out=0;
for(int i=((N/2)+1);i<=N;i++)
{
out+=dp[i][N];
}
printf("%.9Lf",out);
}  


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

int main() {
  string S, T;
  cin >> S >> T;
  int sum = 0;
  for (int i =0; i < S.size(); i++){
    if(S.at(i) == T.at(i)){
      sum += 1;
    }
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
float n;
float arr[105];
int main() {
	
	 cin >> n;
	
	for (int i = 0; i < n; i++) {
		float a; cin >> a;
		arr[i] = (1 / a);
	}
	float res = 0;
	for (int i = 0; i < n; i++) {
		res += arr[i];
	}

	cout <<  1/res;





	return 0;
}

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

long long n,k,v[2005],cont,tmp,ans,mod=1e9+7ll;

int main(){

	cin>>n>>k;
	
	for(int i=0;i<n;i++)cin>>v[i];
	
	for(int i=0;i<n;i++){
        cont=tmp=0;
        for(int j=0;j<n;j++){
            if(v[j]<v[i])cont++;
            if(v[j]<v[i] && j>i)tmp++;    
        }
        
        ans+=((2ll*tmp+cont*(k-1ll))%mod*((k*((mod+1ll)/2ll))%mod))%mod;
        
        //cout<<ans<<endl;
        ans%=mod;
	}
	
	cout<<ans<<endl;

return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 1e18
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define arr array
#define _lower_bound(a, x) lower_bound(a.begin(), a.end(), x) - a.begin()
#define _upper_bound(a, x) upper_bound(a.begin(), a.end(), x) - a.begin()
#define _debug(x) cout << #x << " = " << x << endl;
#define _sort(x) sort(x.begin(), x.end())
#define _rsort(x) sort(x.rbegin(), x.rend())
#define _reverse(x) reverse(x.begin(), x.end())
typedef long long ll;
using namespace std;

void solve() {
	int n, cnt = 0, l = 0; cin >> n;
	string s; cin >> s;
	for (int i = n - 1; i >= 1; --i) {
		if (s[i] == 'R') {
			bool flag = false;
			for (int j = l; j < i; ++j) {
				if (s[j] == 'W') {
					l = j;
					flag = true;
					swap(s[i], s[j]);
					++cnt;
					break;
				}
			}
			if (!flag) break;
		}
	}
	// for (int i = 1; i < n; ++i) {
	// 	if (s[i] == 'R' && s[i - 1] == 'W') {
	// 		bool flag = false;
	// 		for (int k = 0; k < i; ++k) {
	// 			if (s[k] == 'W') {
	// 				flag = true;
	// 				++cnt;
	// 				swap(s[i], s[k]);
	// 				break;
	// 			} 
	// 		}
	// 		if (!flag) {
	// 			s[i - 1] = 'R';
	// 			++cnt;
	// 		} 
	// 	}
	// }
	cout << cnt << endl;
}   

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

    // int t; cin >> t;
    // while(t--) 
        solve();
}

Measured memory_bytes: 3744
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define M 1000000007

int32_t main()
{   fast

    int n;
    cin>>n;
    int d[n];
    for(int i=0;i<n;i++)
        cin>>d[i];
        int ans=0;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
          ans+=d[i]*d[j];
        }
    }
    cout<<ans;
    return 0;
}


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

int main() {
  int N;
  cin>>N;
  int see =1;
  int H[N];
  for(int i=0;i<N;i++){
    cin>>H[i];
  }
  for(int i=1;i<N;i++){
    int k=i;
    
    while(k>0){
      if(H[i]>=H[k-1]){
	k--;
      }else{
	break;
      }
      if(k<=0) see++;
    }
    
  }
  cout<<see<<endl;
  return 0;
}


Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-9;

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

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

	cin >> N >> K;
	vector<int>v(N);
	for (int i = 0; i < K; i++) {
		cin >> M;
		for (int j = 0; j < M; j++) {
			cin >> L;
			v[L - 1]++;
		}
	}
	for (auto &i : v)i = !i;
	cout << accumulate(v.begin(), v.end(), 0) << endl;
}


Measured memory_bytes: 3636
X,Y=map(int,input().split())
mod=10**9+7
if (X+Y)%3!=0:
    print(0);exit()
if X*2<Y or Y*2<X:
    print(0);exit()
t=(X+Y)//3
f=[1]
for i in range(1,t+100):
    f.append(f[-1]*i%mod)
def comb(a,b,m):
    return f[a]*pow(f[b],m-2,m)*pow(f[a-b],m-2,m)%m
print(comb(t,X-t,mod))


Measured memory_bytes: 29460
#include<iostream>
using namespace std;
#define MAX 500000
#define SENTINEL 2000000000

int L[MAX / 2 + 2], R[MAX / 2 + 2];
int cnt;

void merge(int A[], int n, int left, int mid, int right) {
	int n1 = mid - left;
	int n2 = right - mid;
	for (int i = 0; i < n1; i++) L[i] = A[left + i];
	for (int i = 0; i < n2; i++) R[i] = A[mid + i];
	L[n1] = R[n2] = SENTINEL;
	int i = 0, j = 0;
	for (int k = left; k < right; k++) {
		cnt++;
		if (L[i] <= R[j]) {
			A[k] = L[i++];
		}
		else {
			A[k] = R[j++];
		}
	}
}

void mergeSort(int A[], int n, int left, int right) {
	if (left + 1 < right) {
		int mid = (left + right) / 2;
		mergeSort(A, n, left, mid);
		mergeSort(A, n, mid, right);
		merge(A, n, left, mid, right);
	}
}

int main() {
	int A[MAX], n, i;
	cnt = 0;

	cin >> n;
	for (i = 0; i < n; i++)cin >> A[i];

	mergeSort(A, n, 0, n);

	for (i = 0; i < n; i++) {
		if (i) cout << " ";
		cout << A[i];
	}
	cout << endl;

	cout << cnt << endl;

	return 0;
}


Measured memory_bytes: 6908
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
using namespace std;

void solve()
{
  int x, a, b;
  cin >> x >> a >> b;

  if(a-b < 0) {
    if(x+(a-b) < 0) {
      cout << "dangerous" << endl;
    } else {
      cout << "safe" << endl;
    }
  } else {
    cout << "delicious" << endl;
  }
}

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

Measured memory_bytes: 256
import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, core.bitop;

enum inf = 1_001_001_001;
enum inf6 = 1_001_001_001_001_001_001L;
enum mod = 1_000_000_007L;



void main() {
    long a, b;
    scan(a, b);
    writeln(a / gcd(a, b) * b);
}

















void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x > arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x < arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 using namespace std;
int main(){
string s;
  int a=0,b=0,c=0,d=0,l;
  cin>>s;
  l= s.length();
  for (int i;i<l;i++){
    if(s.at(i)=='N'){a++;}
    if(s.at(i)=='E'){b++;}
    
    if(s.at(i)=='S'){c++;}
        
    if(s.at(i)=='W'){d++;}
     
  }
  if ((a!=0 && c==0)||(a==0 && c!=0)||(d==0 && b!=0)||(b==0 && d!=0))
      {cout<<"No"<<endl;}
  else {cout<<"Yes"<<endl;}

return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

a, b = LI()
print(max(a+b, a-b, a*b))

Measured memory_bytes: 65540
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n; cin >> n;
  ll mx = n;
  int ans = 0;
  while(mx > 1) {
    mx = max((mx + 2) / 3, mx - (2 * mx + 6) / 3);
    ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3192
#include <bits/stdc++.h>
using namespace std;
int a[100100];
int sum[110][110];
int main()
{
    int h,w;
    while(cin>>h>>w)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        int k=1;
        int s=1;
        for(int i=1;i<=h;i++)
        {
            if(i%2)
            {
                for(int j=1;j<=w;j++)
                {
                    if(a[s])
                    {
                        sum[i][j]=s;
                        a[s]--;
                    }
                    else
                    {
                        s++;
                        sum[i][j]=s;
                        a[s]--;
                    }
                }
            }
            else
            {
                for(int j=w;j>=1;j--)
                {
                    if(a[s])
                    {
                        sum[i][j]=s;
                        a[s]--;
                    }
                    else
                    {
                        s++;
                        sum[i][j]=s;
                        a[s]--;
                    }
                }
            }
        }
        for(int i=1;i<=h;i++)
        {
            for(int j=1;j<=w;j++)
                cout<<sum[i][j]<<" ";
            cout<<endl;
        }
    }
}


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

using LL = long long;

vector<vector<int>> next(const auto& P, const auto& I, auto end) {
  vector<vector<int>> res(P.size());
  set<int> S;
  for(auto p: P) {
    set<int> remove;
    for(auto x: S) {
      if(p < x) break;
      res[x].emplace_back(I[p]);
      if(res[x].size() == 2) remove.emplace(x);
    }
    for(auto x: remove) S.erase(x);
    S.emplace(p);
  }
  for(auto& x: res) while(x.size() != 2) x.emplace_back(end);
  return res;
}

int main() {
  int N;
  cin >> N;
  vector<int> P(N), I(N);
  for(auto i = 0; i < N; ++i) {
    cin >> P[i];
    I[--P[i]] = i;
  }

  auto R = next(P, I, N);
  reverse(begin(P), end(P));
  auto L = next(P, I, -1);

  LL ans = 0;
  for(auto x = 0; x < N; ++x) {
    LL l1 = I[x]    - L[x][0];
    LL l2 = L[x][0] - L[x][1];
    LL r1 = R[x][0] - I[x];
    LL r2 = R[x][1] - R[x][0];
    ans += (x + 1) * (l1 * r2 + l2 * r1);
  }
  cout << ans << endl;
}


Measured memory_bytes: 16000
// https://beta.atcoder.jp/contests/abc077
// status:

#define SUBMIT
//#define DEBUG

#include <utility>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <queue>
#include <numeric>
#include <limits>

using namespace std;
using ui64 = unsigned long long;
using i64 = long long;

const int MAX_K = 100000;
const int INF = 1 << 20;
int K;
int dist[MAX_K];

// (i-th node, distance) pair
deque<pair<int, int>> q;

int bfs() {
    q.push_back(make_pair(1, 0));

    while (!q.empty()) {
        auto p = q.front();
        q.pop_front();

        if (dist[p.first] != INF) continue;
        dist[p.first % K] = p.second;
        if (p.first == 0) break;

        q.push_back(make_pair((p.first + 1) % K, p.second + 1));
        q.push_front(make_pair((p.first * 10) % K, p.second));
    }

    return dist[0] + 1;
}

int main() {
#ifdef SUBMIT
    auto& stream = cin;
#else
    auto program_input = std::string(R"(6
)");
    stringstream stream(program_input);
#endif
    stream >> K;
    for (int i = 0; i < K; ++i) dist[i] = INF;

    auto ans = bfs();
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <cstdio>
#define MAX 101
using namespace std;

int n;
int a[MAX][MAX]={};
int d[MAX];

void track(int v,int depth){
  if(d[v]>depth||d[v]==-1){
    d[v]=depth;
  }else if(d[v]<depth){
    return;
  }
  for(int i=1;i<=n;i++){
    if(a[v][i]==1){
      track(i,depth+1);
    }
  }
}

int main(){
  cin>>n;
  for(int i=1;i<=n;i++){
    int u,k; cin>>u>>k;
    for(int j=0;j<k;j++){
      int v; cin>>v;
      a[i][v]=1;
    }
  }

  for(int i=1;i<=n;i++){
    d[i]=-1;
  }

  track(1,0);

  for(int i=1;i<=n;i++){
    cout<<i<<" "<<d[i]<<endl;
  }
}

Measured memory_bytes: 3100
#include<iostream>
using namespace std;
int a,b,c,ans;
int main()
{
	cin >> a >> b >> c;
	for (int i = 1;i <= a;i ++)
	{
		int d;
		cin >> d;
		if(d<b||d>=c)ans++;
	}
	cout<<ans<<endl;
}

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

#define mp          make_pair
#define pb          push_back
#define ff          first
#define ss          second
#define ii          pair<int,int>
#define mod         (int)1e9+7
#define inf         1e18
#define max_v       200005

typedef long long int lli;
typedef long double ld;

#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

lli dp[105][100005];

lli func(int n,int W,lli w[],lli val[])
{
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=W;j++)
        {
            if(i==0 || j==0)
                dp[i][j]=0;
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=W;j++)
        {
            if(w[i-1]<=j)
                dp[i][j]=max(dp[i-1][j],val[i-1]+dp[i-1][j-w[i-1]]);
            else
                dp[i][j]=dp[i-1][j];
        }
    }
    return dp[n][W];
}

void solve() 
{
    lli n,W;
    cin>>n>>W; 
    lli w[n],val[n];
    for(int i=0;i<n;i++)
    {
        cin>>w[i];
        cin>>val[i];
    }

    cout<<func(n,W,w,val)<<endl;
    // for(int i=1;i<=n;i++)
    // {
    //     for(int j=1;j<=W;j++)
    //     {
    //         cout<<dp[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    return ;
}

int main()
{
    fio

    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
 
    int t;
    t=1;
//    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 82476
import math

A, B = map( int, input().split() )
m, M = B * 10 , A * 13

ans = -1
for x in range( m, M + 1 ):
  if ( math.floor( x * 0.08 ) == A ) and ( math.floor( x * 0.1 ) == B ):
    ans = x
    break
print(ans)
  
  

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <bitset>
#include <tuple>
#include <stack>
#include <utility>

using namespace std;
typedef long long ll;

int main(){
    ll N, K, X=0;
    cin >> N >> K;
    vector<ll> A(N);
    for(ll i=0; i<N; i++) cin >> A[i];
    for(ll i=40; i>=0; i--){
        ll k0 = 0, k1 = 0;
        for(ll n=0; n<N; n++){
            if((A[n]>>i)&1){
                k1 += 1;
            }
            else k0 += 1;
        }
        if(k1 < k0){
            X += pow(2,i);
            if(X > K){
                X -= pow(2,i);
            }
        }
    }
    ll ans = 0;
    for(ll i=0; i<N; i++){
        ans += (X ^ A[i]);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
bool isValid(vector<int>&v1,vector<int>&v2){
    int value = 0;
    for(int i = 0; i < v1.size(); i++){
        value += pow(v1[i]-v2[i],2);
    }
    for(int i = 1; i <= (value); i++){
        if((i*i)==value){
            return true;
        }
    }
    return false;
}
int main(){
    int n,d;
    cin >> n >> d;
    vector <vector<int>> x(n,vector<int>(d));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < d; j++){
            cin >> x[i][j];
        }
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        for(int j = (i+1); j < n; j++){
           if(isValid(x[i],x[j])){
               ans++;
           }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int h1,m1,h2,m2,k;
    cin>>h1>>m1>>h2>>m2>>k;
    int res=(h2*60+m2)-(h1*60+m1)-k;
    cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <map>
#include <set>
#include "math.h"
using namespace std;
#define ULONGLONG unsigned long long

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

	std::map<unsigned long long, unsigned long long> divisors;
	unsigned long long currentN = N;
	ULONGLONG i = 2u;
	while ((currentN != 1) && (i < (N / (i-1))))
	{
		unsigned long long count = 0;
		while (currentN % i == 0)
		{
			count++;
			currentN /= i;
		}
		divisors[i] = count;

		i++;
	}

	ULONGLONG result = 0u;
	if (currentN != 1)
	{
		result = 1u;
	}

	for (auto it = divisors.begin(); it != divisors.end(); it++)
	{
		ULONGLONG remaining = it->second;
		ULONGLONG lastValue = 0u;
		ULONGLONG currentValue = 1u;
		while (remaining > lastValue)
		{
			ULONGLONG z = pow(it->first, currentValue);
			N /= z;

			lastValue = currentValue;
			remaining -= currentValue;
			currentValue++;
			result++;
		}
	}

	cout << result << endl;
	return 0;
}

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

int main(void){
    
    int N;
    int ans = 0;

    cin >> N;
    int A[100];
    int B[100];
    int C[100];
    // 配列に値を格納
    for (int i = 0;i < N ;i++) {
        
        cin >> A[i];
        --A[i];
    }     
    for (int i = 0;i < N ;i++) {
        
        cin >> B[i];        
    }    
    for (int i = 0;i < (N-1) ;i++) {
        
        cin >> C[i];        
    }
    // 配列Bの値はすべて合計
    for (int i = 0 ;i < N ;i++){
        
        ans += B[i];
    } 
  	int temp = 1000;
    for (int i = 0 ; i < N ;i++){
        
        if (i > 0 && temp == A[i]-1) {
            ans += C[A[i-1]]; 
        }
    	temp = A[i];
    }
    cout << ans <<endl;
    return 0;
}

Measured memory_bytes: 256
package main

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

func main() {
	N := readint()
	A := make(map[int]int, N)
	unique := true
	for i := 0; i < N; i++ {
		ai := readint()
		if _, ok := A[ai]; ok {
			unique = false
		}
		A[ai] = ai
	}
	if unique {
		fmt.Println("YES")
	} else {
		fmt.Println("NO")
	}
}

const (
	iobufsize = 1 * 1024 * 1024 // 1 MB
)

var stdinsc = func() *bufio.Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Buffer(make([]byte, iobufsize), iobufsize)
	sc.Split(bufio.ScanWords)
	return sc
}()

func readint() int {
	stdinsc.Scan()
	v, err := strconv.Atoi(stdinsc.Text())
	if err != nil {
		panic(err)
	}
	return v
}

func readstr() string {
	stdinsc.Scan()
	return stdinsc.Text()
}

func pow(x, y int) int {
	if y < 1 {
		return 1
	}
	return x * pow(x, y-1)
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}


Measured memory_bytes: 9472
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<tuple>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-15
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	string S;
	string T="";
	string sub[4]={"dream","dreamer","erase","eraser"};
	int flag=1;
	int now=0;
	scan(S);
	rep(i,S.size()){
		int breakflag=0;
		rep(j,4){
			if(S.substr(now)==sub[j]){
				breakflag=1;
				T+=S.substr(now);
			}
		}
		if(breakflag||now==S.size()) break;
		if(S.substr(now,5)==sub[0]){
			if(S.substr(now+5,4)=="erer"||S.substr(now+5,4)=="erdr"){
				now+=sub[1].size();
				T+=sub[1];
			}
			else{
				now+=sub[0].size();
				T+=sub[0];
			}
		}
		else if(S.substr(now,5)==sub[2]){
			if(S.substr(now,6)==sub[3]){
				now+=sub[3].size();
				T+=sub[3];
			}
			else{
				now+=sub[2].size();
				T+=sub[2];
			}
		}
		else{
			flag=0;
			break;
		}
		//prin(T);
	}
	if(flag) prin("YES");
	else prin("NO");
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using ll = long long;
typedef pair<int, int> P;
ll Mod = 1000000007;
int main() {
  int a,b;
  cin >> a >> b;
  if ((a * b) % 2 == 0) {
    cout << "Even" << endl;
  } else {
    cout << "Odd" << endl;
  }
  return 0;
}

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

using namespace std;

int main()
{
  long long int a,b,n;
  cin>>a>>b>>n;
  long long int x;
  long long int maks=0;
  if(b>n)
  {
      x=n;
      long long int prv=(a*x)/b;
        long int vtor=x/b;
      cout<<prv-a*vtor<<endl;
  }else
  {
          x=b-1;
          long long int prv=(a*x)/b;
          long int vtor=x/b;
          cout<<prv-a*vtor<<endl;
  }
}


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

ll dp[100000*100+7];
ll weight[107], value[107];

int main()
{
    memset( dp, 0x3f, sizeof(dp) );

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

    int n,w;
    cin>>n>>w;

    ll tot_sum= 0;

    /// dp[i]-> minimum total weight by taking items with sum of value exactly i

    for( int i=0;i<n;i++ )
        cin>>weight[i]>>value[i], tot_sum+= value[i];

    dp[0]= 0;

    for( int i=0;i<n;i++ )
        for( int value_already=tot_sum-value[i];value_already>=0;value_already-- )
            dp[ value_already+value[i] ]= min( dp[ value_already+value[i] ], dp[ value_already ]+weight[i] );

    ll ans= 0;

    for( int i=0;i<=tot_sum;i++ )
        if( dp[i]<=w )
            ans= i;

    cout<< ans <<endl;
}


Measured memory_bytes: 78336
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <fstream>
#include <numeric>
#include <bitset>
#include <sstream>

using namespace std;

#define max(a,b) a > b ? a : b
#define min(a,b) a < b ? a : b

int A,B;

int main() {

    cin >> A >> B;

    cout << (A * B) << endl;

    return 0;
}

Measured memory_bytes: 3636
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main(){
  map<char,int> mp;
  string s;
  cin>>s;
  for(int i=0;i<s.size();++i){
    mp[s[i]]+=1;
  }
  bool flag=false;
  for(auto itr = mp.begin(); itr != mp.end(); ++itr) {
    if(itr->second%2!=0)flag=true;
    }
  if(!flag)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MAX_N=1e6; // 1e8=x, 1e7=? 1e6=o                                                                                                                                                     
int n[MAX_N+1]={},prime[1000100];
void eratos_sieve(){
  for(int i=2;i<=MAX_N;i++) if(!n[i]){
      prime[i]=1;
      for(int j=i;j<=MAX_N;j+=i) n[j]=1;
  }
}
int main(){
  eratos_sieve();
  for(int a,b,n;cin>>a>>b>>n,a;){
    int r=0;
    for(;r!=n;a+=b) r+=prime[a];
    cout<<a-b<<endl;
  }
  return 0;
}

Measured memory_bytes: 10812
// https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_a

#include <bits/stdc++.h>
#define REP(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define REPR(i, n) for (int(i) = (n); (i) >= 0; (i)--)
#define FOR(i, m, n) for (int(i) = (m); (i) < (n); i++)
#define INF 1e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

int main()
{
  int N, K;
  cin >> N >> K;

  cout << (K == 1 ? 0 : (N - K)) << '\n';

  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
using namespace std;
int main(){
  unsigned int data[4 * 3 * 10] = {0};

  int n;
  cin >> n;
  for(int i = 0 ; i < n ; i++){
    int b, f, r, v;
    cin >> b >> f >> r >> v;

    b--;
    f--;
    r--;

    data[(b*30)+(f*10)+r] += v;
  }

  for (int i = 0; i < 4 * 3 * 10; i++) {
    if (i != 0 && i % 10 == 0) printf("\n");
    if (i != 0 && i % (10 * 3) == 0) printf("####################\n");
    cout << " "<< data[i];
  }
  printf("\n");

}

Measured memory_bytes: 3076
#include<bits/stdc++.h>
using namespace std;
#define ll long long int

ll n;
ll a[100005][3];
ll dp[100005][3];

ll fun(ll r, ll c){
    if(r==n)return 0;
    ll& ans=dp[r][c];
    if(ans!=-1)return ans;
    ll c1,c2;
    if(c==0){
        c1=1,c2=2;
    }
    else if(c==1){
        c1=0,c2=2;
    }
    else {
        c1=0,c2=1;
    }
    return ans=a[r][c]+max(fun(r+1,c1),fun(r+1,c2));
}

int main() {
    cin>>n;
    for(ll i=0;i<n;i++){
        cin>>a[i][0]>>a[i][1]>>a[i][2];
        dp[i][0]=-1,dp[i][1]=-1,dp[i][2]=-1;
    }
    cout<<max(fun(0,0),max(fun(0,1),fun(0,2)));
}

Measured memory_bytes: 12892
H,W = map(int,input().split())
Data = []
for i in range(10):
    Data.append(list(map(int,input().split())))
Wall = []
for _ in range(H):
    Wall.append(list(map(int,input().split())))

for k in range(10):
    for i in range(10):
        for j in range(10):
            Data[i][j] = min(Data[i][j],Data[i][k]+Data[k][j])
ans = 0
for h in range(H):
    for w in range(W):
        num = Wall[h][w]
        if num != -1:
            ans += Data[num][1]
print(ans)


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

int main(){
    int a, b;
    cin >> a >> b;
    int count = 0;
    
    for (int i = a; i <= b; i++){
        int n = i;
       vector<int> x(5);
        for (int j = 0; j < 5; j++){
            x.at(j) = n % 10;
            n /= 10;
        }
        
        if (x.at(0) == x.at(4) && x.at(1) == x.at(3)){
            count++;
        }
    }
    
    cout << count << endl;
}

Measured memory_bytes: 256