akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
 
int main(){
    int K;
    string S;
    cin >> K >> S;
    int N=S.size();
    if(N<=K){
        cout << S << endl;
    }
    else{
        rep(i,K){
            cout << S.at(i);
        }
        cout << "..." << endl;
    }
 
}

Measured memory_bytes: 3600
mod = 10**9 + 7

def power(p, e):
  ret = 1
  while(e):
    if(e & 1):
      ret *= p
      ret %= mod
    p *= p
    e >>= 1
  return ret

N = int(input())
C = list(map(int, input().split()))
C.sort()

f = 0
for i in range(N):
  f += (N - i + 1) * C[i]
  f %= mod

f *= power(2, N - 1)**2 % mod
f %= mod
print(f)

Measured memory_bytes: 26024
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
  int N = sc.nextInt();
  Set<String> s = new HashSet<String>();
  int counter = 0;
  for(int i = 0;i < N;i++){
    int a = sc.nextInt();
    if(a < 400)s.add("a");
    else if(a < 800)s.add("b");
    else if(a < 1200)s.add("c");
    else if(a < 1600)s.add("d");
    else if(a < 2000)s.add("e");
    else if(a < 2400)s.add("f");
    else if(a < 2800)s.add("g");
    else if(a < 3200)s.add("h");
    else if(a >= 3200)counter++;
  }
  if(s.size() == 0){
    System.out.println("1");
  }
  else{
    System.out.print(s.size() > 8 ? "8" : s.size());
  }
  System.out.print(" ");
  System.out.println(s.size() + counter);
}}


Measured memory_bytes: 21712
using System;
    using System.Linq;
     
    namespace atcoderTest
    {
        public class Program
        {
    		public static void Main(string[] args)
    		{
    			// 文字列の入力
    			string a = Console.ReadLine();
    			// 異なる文字列が含まれているか判定する
     
    			if (a.Distinct().Count() > 1)
    			{
    				Console.Write("Yes");
    			}
    			else
    			{
    				Console.Write("No");
    			}
    		}
    	}
    }

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

int main() {
	int a, b, k;
	cin >> a >> b >> k;


	int num;
	int cnt = 0;
	int ans = 0;


	if (a < b) {
		num = b;
	} else {
		num = a;
	}
	for (int i = num; 0 < i; i--) {
		if (a % i == 0 && b % i == 0) {
			cnt++;
		}
		if (cnt == k) {
			ans = i;
			break;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int N, K;
vector<int> A(200100);

bool ok(int x)
{
    ll cnt = 0;
    for (int i = 0; i < N; i++)
    {
        if (A[i] > x)
            cnt += (A[i] - 1) / x;
    }
    if (cnt <= K)
        return true;
    return false;
}

int main()
{
    cin >> N >> K;
    for (int i = 0; i < N; i++)
        cin >> A[i];
    int l = 0, r = 1000000000;
    while (r - l > 1)
    {
        int m = (l + r) / 2;
        if (ok(m))
            r = m;
        else
            l = m;
    }
    cout << r << endl;
}


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

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

using namespace std;

typedef long long int lli;
typedef vector<int> vi;

lli number(vector<lli> t, vector<bool>c) {
	lli i, j, k, n;
	k = t.size();

	n = 0;
	j = t[0];
	rep(i, k-1) {
		if (c[i] == true) {
			n += j;
			j = t[i + 1];
		}
		else {
			j = j * 10 + t[i + 1];
		}
	}
	n += j;

	return n;
}

int main() {
	lli i, j, k, n;
	string s;
	vector<bool>ope;
	vector<lli> t;
	bool carry;

	cin >> s;

	k = s.length() - 1;

	if (k == 0) {
		cout << s;
		return 0;
	}
	t.resize(k + 1);
	rep(i, k + 1) {
		t[i] = s[i] - '0';
	}

	ope.resize(k);

	rep(i, k) {
		ope[i] = false;
	}
	ope[0] = true;

	i = 0;
	rep(j, k + 1) {
		i = i * 10 + t[j];
	}

	while (true) {
		i += number(t, ope);
		carry = true;
		j = 0;
		while (carry) {
			carry = ope[j];
			ope[j] = !ope[j];
			j++;
			if (j == k + 1)
				break;
		}
		if (j == k + 1)
			break;
	}

	cout << i;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>

using namespace std;

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

int card[200];
int n, m;

void kshuf(int k) {
	int tmp[200];
	memcpy(tmp, card, sizeof(card));

	FOR(i, 0, 2*n - k) card[i] = tmp[i + k];
	FOR(i, 2*n - k, n*2) card[i] = tmp[i - (2*n - k)];
}

void rshuf() {
	int tmp[200];
	memcpy(tmp, card, sizeof(card));

	REP(i,n) {
		card[2*i] = tmp[i];
		card[2*i + 1] = tmp[i + n];
	}
}

int main() {
	cin >> n >> m;
	REP(i,n*2) card[i] = i+1;

	REP(i,m) {
		int tmp;
		cin >> tmp;
		if (tmp == 0) rshuf();
		else kshuf(tmp);
	}

	REP(i,2*n) cout << card[i] << endl;

	return 0;
}

Measured memory_bytes: 1160
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <iostream>
#include <sstream>
#include <climits>
#include <cfloat>
#include <complex>


typedef long long ll;
const double Eps = 1e-5;

using namespace std;

int main()
{
	char buf[1024 + 256];
	cin.getline(buf, sizeof(buf));
	int n;
	sscanf(buf, "%d", &n);
	while (n--)
	{
		cin.getline(buf, sizeof(buf));
		strcat(buf, "--");
		pair<int, char> pos[26];
		for (int i = 0; i < 26; ++i)
		{
			pos[i].first = 9999;
			pos[i].second = i + 'a';
		}
		int relaPos = 0;
		for (int i = 0; buf[i] != '\0'; i += 3)
		{
			pos[buf[i] - 'a'].first = relaPos;
			if (buf[i + 2] == '>')
				++relaPos;
			else
				--relaPos;
		}
		sort(pos, pos+26);
		for (int i = 0; pos[i].first != 9999 && i < 26; ++i)
			putchar(pos[i].second);
		putchar('\n');
	}

	return 0;
}

Measured memory_bytes: 0
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 100001; //check the limits, dummy
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);    
	
    int N; cin >> N;
    vi A(N), B(N); F0R(i, N) cin >> A[i] >> B[i];
    sort(all(A));
    sort(all(B));
    ll X, Y; 
    if (N % 2 == 1) {
        X = A[N/2];
        Y = B[N/2];
    } else {
        X = A[N/2 - 1] + A[N/2];
        Y = B[N/2 - 1] + B[N/2];
    }

    cout << Y-X+1 << nl;
	
	return 0;
}
 
// read the question correctly (ll vs int)
// template by bqi343



Measured memory_bytes: 4836
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
#include <map>
#include <time.h>
#include <iomanip>
#include <bitset>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod (ll)(1e9+7)
#define int ll

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

string ar[301];
int ans[301][301];

signed main() {
    int h, w, k;
    cin >> h >> w >> k;

    rep(i, 0, h) {
        cin >> ar[i];
    }

    int count = 1;
    int line = 1;
    rep(i, 0, h) {
        bool flag = false;
        int zen = 0;
        rep(j, 0, w) {
            if(ar[i][j] == '#') {
                flag = true;
                rep(k, 0, line) {
                    rep(l, zen, w) {
                        ans[i - k][l] = count;
                    }
                }
                count++;
                zen = j + 1;
            }
        }
        if(!flag) {
            line++;
        }else {
            line = 1;
        }
        if(i == h - 1 && line > 1) {
            int ki;
            dep(j, h - 1, 0) {
                if(ans[j][0]) {
                    ki = j;
                    break;
                }
            }
            rep(j, 0, line) {
                rep(k, 0, w) {
                    ans[i - j][k] = ans[ki][k];
                }
            }
        }
    }

    rep(i, 0, h) {
        rep(j, 0, w) {
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
}


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

using namespace std;

int main(int argc, char const *argv[])
{
    int N;
    cin >> N;
    vector<string> S;
    S.resize(N);
    vector<int> C(4);
    fill(C.begin(), C.end(), 0);
    for (int i = 0; i < N; i++)
    {
        cin >> S[i];
        if(S[i] == "AC") C[0]++;
        if(S[i] == "WA") C[1]++;
        if(S[i] == "TLE") C[2]++;
        if(S[i] == "RE") C[3]++;
    }
    
    cout << "AC x " << C[0] << endl;
    cout << "WA x " << C[1] << endl;
    cout << "TLE x " << C[2] << endl;
    cout << "RE x " << C[3] << endl;

    return 0;
}

Measured memory_bytes: 6424
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <deque>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;

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

	auto ans = 0;
	for (auto i = 0; i < 1000; ++i)
	{
		int num[] = { i / 100, i / 10 % 10, i % 10 };
		int index = 0;
		for (auto j = 0; j < (int)S.size(); ++j)
		{
			if (S[j] - '0' == num[index])
			{
				++index;
				if (index >= 3)
				{
					++ans;
					break;
				}
			}
		}
	}

	cout << ans << endl;

	return 0;
}

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

using namespace std;

#define ll long long

int main(){

	int n, x;
	cin >> n;
	x = n;
        map<string, int> mp;
        cin.ignore();

	ll cnt = 0;
	while(n--){
		string s;
		getline(cin, s);
		sort(s.begin(), s.end());
		cnt += mp[s];
		mp[s]++;
	}

	cout << cnt;

	return 0;
}


Measured memory_bytes: 11136
import java.util.*;
import java.io.*;

class Main{
    public static void main(String args[])throws IOException{
      try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))){
        String[] input = br.readLine().split(" ");
        String[] attack_input = br.readLine().split(" ");

        int H = Integer.parseInt(input[0]);
        int N = Integer.parseInt(input[1]);

        int tmp = 0;

        for(int i = 0; i < N; i++){
          tmp = Integer.parseInt(attack_input[i]);
          H -= tmp;
        }

        if(H <= 0){
          System.out.println("Yes");
        }else{
          System.out.println("No");
        }
      }
    }
}

Measured memory_bytes: 32472
import heapq
N,K=map(int, input().split())
V=list(map(int, input().split()))
ans=0

for i in range (0,min(N,K)+1):
    for j in range(0,min(N,K)+1-i):
        CNT = []
        tmp =K-(i+j)
        for k in range(0,i):
            CNT.append(V[k])
        for l in range(0,j):
            CNT.append(V[N-1-l])
        heapq.heapify(CNT)
        for h in range(0,tmp):
            if len(CNT)>0 and CNT[0]<0:
                heapq.heappop(CNT)
        ans=max(ans,sum(CNT))

print(ans)

Measured memory_bytes: 53724
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;

#define rep(i,a) for(int i=0; i<a; i++)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define loop3(i,j,k,a) for(int i=0; i<a; i++)for(int j=0; j<a; j++)if(i!=j)for(int k=0; k<a; k++)if(i!=k&&j!=k)
#define loop4(i,j,k,l,a) for(int i=0; i<a; i++)for(int j=0; j<a; j++)if(i!=j)for(int k=0; k<a; k++)if(i!=k&&j!=k)for(int l=0; l<a; l++)if(i!=l&&j!=l&&k!=l)
#define rep1(i,a) for(int i=1; i<=a; i++)

#define scnd1(a) scanf("%d", &a)
#define scnd2(a,b) scanf("%d%d", &a,&b)
#define scnd3(a,b,c) scanf("%d%d%d", &a,&b,&c)
#define scnd4(a,b,c,d) scanf("%d%d%d%d", &a,&b,&c,&d)

#define cin1(a) cin >> a;
#define cin2(a,b) cin >> a >> b;
#define cin3(a,b,c) cin >> a >> b >> c;
#define cin4(a,b,c,d) cin >> a >> b >> c >> d;
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define prtd1(a) printf("%d\n", a)
#define prtd2(a,b) printf("%d %d\n", a,b)
#define prtd3(a,b,c) printf("%d %d %d\n", a,b,c)
#define prtd4(a,b,c,d) printf("%d %d %d %d\n", a,b,c,d)

#define mem(a,n) memset( a, n, sizeof(a))
#define INF 1000000000
typedef long long ll;
typedef pair<long long, int> P;

const int MAX_E=200010;
struct edge{int u,v; ll cost;};
edge es[MAX_E];

int V, E;
int par[100009];
int height[100009];

void init(int n){
    for(int i=0; i<n; i++){
        par[i]=i;
        height[i]=0;
    }
}

int find(int x){
    if(par[x]==x) return x;
    else return par[x]=find(par[x]);
}

void unite(int x, int y){
    x=find(x);
    y=find(y);
    if(x==y) return;
    if(height[x]<height[y]){
        par[x]=y;
    }else{
        par[y]=x;
        if(height[x]==height[y]) height[x]++;
    }
}

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

bool comp(const edge& e1, const edge& e2){
    return e1.cost < e2.cost;
}

int cruscal(){
    sort(es, es+E, comp);
    init(V);
    int res=0;
    rep(i,E){
        edge e=es[i];
        if(!(find(e.u) == find(e.v))){
            unite(e.u,e.v);
            res+=e.cost;
        }
    }
    return res;
}

int main() {
    cin>>V;
    P x[V];
    P y[V];
    
    rep(i,V){
        cin>>x[i].first>>y[i].first;
        x[i].second=i; y[i].second=i;
    }
    sort(x,x+V);
    rep(i,V-1){ es[i] = { x[i].second, x[i+1].second, x[i+1].first - x[i].first};}
    
    sort(y,y+V);
    rep(i,V-1){ es[i+V-1] = { y[i].second, y[i+1].second, y[i+1].first - y[i].first};}
    
    E = V*2-2;
    cout<<cruscal()<<endl;
}

Measured memory_bytes: 7424
import math

N=int(input())
A=int(input())
B=int(input())
C=int(input())
D=int(input())
E=int(input())

if min(A,B,C,D,E)>=N:
    print(5)
else:
    print(math.ceil(N/min(A,B,C,D,E))+4)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define mod 1000000007
#define mod998 998244353
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;

int H, W, L[300], R[300], dp[300][300];
char c[300][300];
int main() {
	int H, W;
	cin >> H >> W;
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			cin >> c[i][j];
		}
	}
	for (int i = 0; i < W - 1; ++i) {
		vector<vector<int>>DP(H + 1, vector<int>(H + 1, intmax));
		vector<vector<int>>a(H, vector<int>(H, 0));
		vector<vector<int>>b(H, vector<int>(H, 0));
		for (int j = 0; j < H; ++j) {
			a[j][j] = (c[0][i] == c[j][i + 1]);
			for (int k = j + 1; k < H; ++k) {
				a[j][k] = a[j][k - 1] + (c[k - j][i] == c[k][i + 1]);
			}
		}
		for (int j = 0; j < H; ++j) {
			b[j][j] = (c[j][i] == c[0][i + 1]);
			for (int k = j + 1; k < H; ++k) {
				b[j][k] = b[j][k - 1] + (c[k][i] == c[k - j][i + 1]);
			}
		}
		DP[0][0] = 0;
		for (int j = 0; j < H; ++j) {
			for (int k = 0; k < H; ++k) {
				int t;
				if (j < k) {
					t = a[k - j][H - 1 - j];
				}
				else {
					t = b[j - k][H - 1 - k];
				}
				DP[j + 1][k] = min(DP[j + 1][k], DP[j][k] + t);
				DP[j][k + 1] = min(DP[j][k + 1], DP[j][k] + t);
			}
		}
		L[i + 1] = R[i] = intmax;
		for (int j = 0; j < H; ++j) {
			L[i + 1] = min(L[i + 1], DP[H][j]);
			R[i] = min(R[i], DP[j][H]);
		}
	}
	for (int i = 0; i < W; ++i) {
		dp[i][i] = L[i] + R[i];
	}
	for (int i = 1; i < W; ++i) {
		for (int j = 0; j + i < W; ++j) {
			dp[j][j + i] = intmax;
			for (int k = 0; k < i; ++k) {
				dp[j][j + i] = min(dp[j][j + i], dp[j][j + k] + dp[j + k + 1][j + i] - max(R[j + k], L[j + k + 1]));
			}
		}
	}
	cout << dp[0][W - 1] << endl;
}

Measured memory_bytes: 1484
# case への対応がだるいなと思ったら
# 右上方向しかない件について
Z = list(map(int, input().split()))
S, T = Z[:2], Z[2:]
dx, dy = [abs(T[i] - S[i]) for i in range(2)]
# first
result = ""
result += "U"*dy
result += "R"*dx
result += "D"*dy
result += "L"*dx
result += "L"
result += "U"*(dy + 1)
result += "R"*(dx + 1)
result += "D"
result += "R"
result += "D"*(dy + 1)
result += "L"*(dx + 1)
result += "U"
print(result)

Measured memory_bytes: 3064
import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;

public class Main
{
    int n;
    int a[] = new int[101];
    
    public static void main(String args[])
    {
	new Main().solve();
    }
    
    void solve()
    {
	in();

	Arrays.sort(a, 0, n);
	
	out(a[n - 1] - a[0]);
    }

    void in()
    {
	Scanner sc = new Scanner(System.in);
	n = sc.nextInt();
	for(int i = 0; i < n; i++) a[i] = sc.nextInt();
    }

    void out()
    {
	
    }
    
    void out(int ans)
    {
	System.out.println(ans);
    }
}


Measured memory_bytes: 23892
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
const ll INF = 1LL << 60;

int main() {
	string S;
	cin >> S;
	for (int i = 0; i < S.size(); i++) {
		if (i % 2 == 0) {
			if (S[i] == 'L') {
				cout << "No" << endl;
				return 0;
			}
		}
		else {
			if (S[i] == 'R') {
				cout << "No" << endl;
				return 0;
			}
		}
	}
	cout << "Yes" << endl;
}

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

int main(){
    int cnt=0;
    string S,T;
    
    cin >> S >> T;
    
    for (int i=0; i<3; i++){
        if (S[i]=='S'||S[i]=='C'||S[i]=='R'){
            if (T[i]=='S'||T[i]=='C'||T[i]=='R'){
                if (S[i]==T[i]) cnt++;
            }
        }
    }
    cout << cnt;
    return 0;
}

Measured memory_bytes: 256
// https://kenkoooo.com/atcoder/#/contest/show/a9a7a4e2-047d-4784-8e13-668951991a1d からきました
// sumから引いていって最小値を更新
package main

import "fmt"

var n int
var a []int

func main() {
	fmt.Scan(&n)
	a = make([]int, n)
	y := 0
	for i := 0; i < n; i++ {
		var j int
		fmt.Scan(&j)
		a[i] = j
		y += j
	}
	if n == 2 {
		fmt.Println(abs(a[0] - a[1]))
		return
	}
	ans := 10000000000
	x := a[0]
	y -= x
	for i := 1; i < n-1; i++ {
		ans = min(ans, abs(x-y))
		x += a[i]
		y -= a[i]
	}
	fmt.Println(ans)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -1 * a
}


Measured memory_bytes: 6400
#include <stdio.h>

void swap (int *x, int *y) {
	int temp;  
 	temp = *x;
	*x = *y;
	*y = temp;
}

int selectionSort(int A[], int n, int c){
	int i,j,minj;
	for(i = 0; i < n; i++){
		minj = i;
		for(j = i; j < n; j++){
			if(A[j] < A[minj]){
				minj = j;
			}
		}
		if(i != minj){
			c++;
		}
		swap(&A[i], &A[minj]);
	}
	return c;
}

int main(void){
	int i, n, c = 0;
	scanf("%d" ,&n);
	int A[n];
	for(i = 0; i < n; i++){
		scanf("%d" ,&A[i]);
	}
	c = selectionSort(A,n,c);
	for (i = 0; i < n; i++){
		if(i < n - 1){
			printf("%d ", A[i]);
		}
		else{
			printf("%d\n", A[i]);
		}
 	}
	printf("%d\n" ,c);
	
	return 0;
}


Measured memory_bytes: 2024
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main(){
  char a[11],b[11],c[11];
  cin>>a>>b>>c;
  a[0]-=32;
  b[0]-=32;
  c[0]-=32;
  cout<<a[0]<<b[0]<<c[0];
}

Measured memory_bytes: 256
S = input()
S = S[::-1]

divide = ["dream", "dreamer", "erase", "eraser"]
for i in range(4):
    divide[i] = divide[i][::-1]

length1 = 0
length2 = 0
can = 0
flag = True

while flag:
    length1 = length2
    for i in range(4):
        if S[length1:length1+len(divide[i])] == divide[i]:
            length2 = length1 + len(divide[i])
    if length1 == length2:
        flag = False

if len(S) == length2:
    print("YES")
else:
    print("NO")

    

Measured memory_bytes: 3188
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>
#include <bitset>
#include <cstdint>

using namespace std;
using lli = long long int;
using i64 = int64_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (lli i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (lli i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

const i64 mod = 1e9 + 7;
i64 n, k;

struct Mat {
  vector<i64> c;

  Mat() : c(n * n) {}
 
  i64& operator()(i64 i, i64 j) { return c[n * i + j]; }
  const i64& operator()(i64 i, i64 j) const { return c[n * i + j]; }
};

Mat dot(const Mat& a, const Mat& b) {
  Mat c;
  for (i64 i = 0; i < n; ++i) {
    for (i64 j = 0; j < n; ++j) {
      for (i64 k = 0; k < n; ++k) {
        c(i, j) = (c(i, j) + a(i, k) * b(k, j)) % mod;
      }
    }
  }
  return c;
}

Mat diag() {
  Mat a;
  for (i64 i = 0; i < n; ++i) a(i, i) = 1;
  return a;
}

Mat pow(const Mat& a, i64 n) {
  Mat b = a, c = diag();
  for (; n > 0; n >>= 1) {
    if (n & 1) c = dot(c, b);
    b = dot(b, b);
  }
  return c;
}

int main() {
  cin >> n >> k;
  Mat a;
  for (i64 i = 0; i < n; ++i) {
    for (i64 j = 0; j < n; ++j) {
      cin >> a(i, j);
    }
  }
  Mat b = pow(a, k);
  i64 ans = 0;
  for (i64 i = 0; i < n; ++i) {
    for (i64 j = 0; j < n; ++j) {
      ans = (ans + b(i, j)) % mod;
    }
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 384
import java.util.*;
import java.util.stream.*;
class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String S = input.next();
        S = S.replaceAll("eraser","-");
        S = S.replaceAll("erase","-");
        S = S.replaceAll("dreamer","-");
        S = S.replaceAll("dream","-");
        S = S.replaceAll("-","");
        if (S.length() == 0){
            System.out.println("YES");
        }else{
            System.out.println("NO");
        }
    }
}

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

int main(){
  string s,t;
  cin >> s >> t;
  
  sort(s.begin(),s.end());
  sort(t.begin(),t.end());
  reverse(t.begin(),t.end());
  
  if(s < t){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func main() {
	sc.Split(bufio.ScanWords)
	Q, H, S, D := getInt(), getInt(), getInt(), getInt()
	N := getInt()

	one := min(Q*4, min(H*2, S))
	two := min(one*2, D)

	n := N / 2
	ans := n * two
	if N%2 == 1 {
		ans += one
	}
	out(ans)
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
#define tpl(...) make_tuple(__VA_ARGS__)
const int INF = 0x3f3f3f3f;
const double EPS = 1e-8;
const double PI = acos(-1);
typedef long long ll;
typedef pair<int,int> pii;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class T>ostream&operator<<(ostream &o,const vector<T>&t){o<<'[';FOR(i,t){if(i!=t.begin())o<<',';o<<*i;}return o<<']';}
template<class S,class T>ostream&operator<<(ostream &o,const pair<S,T>&t){return o<<'('<<t.first<<','<<t.second<<')';}
template<int N,class Tp>void output(ostream&,const Tp&){}
template<int N,class Tp,class,class ...Ts>void output(ostream &o,const Tp&t){if(N)o<<',';o<<get<N>(t);output<N+1,Tp,Ts...>(o,t);}
template<class ...Ts>ostream&operator<<(ostream&o,const tuple<Ts...>&t){o<<'(';output<0,tuple<Ts...>,Ts...>(o,t);return o<<')';}
template<class T>void output(T t,char z=10){if(t<0)t=-t,putchar(45);int c[20];
int k=0;while(t)c[k++]=t%10,t/=10;for(k||(c[k++]=0);k;)putchar(c[--k]^48);putchar(z);}
template<class T>void outputs(T t){output(t);}
template<class S,class ...T>void outputs(S a,T...t){output(a,32);outputs(t...);}
template<class T>void output(T *a,int n){REP(i,n)output(a[i],i!=n-1?',':10);}
template<class T>void output(T *a,int n,int m){REP(i,n)output(a[i],m);}
template<class T>bool input(T &t){int n=1,c;for(t=0;!isdigit(c=getchar())&&~c&&c-45;);
if(!~c)return 0;for(c-45&&(n=0,t=c^48);isdigit(c=getchar());)t=10*t+c-48;t=n?-t:t;return 1;}
template<class S,class ...T>bool input(S&a,T&...t){input(a);return input(t...);}

char s[1010];

ll term(int &i);
ll fact(int &i);

ll exp(int &i) {
  ll p = term(i);
  while(s[i]=='+' || s[i]=='-') {
    char c = s[i++];
    if (c == '+') {
      ll a = term(i);
      p += a;
    }
    else p -= term(i);
  }
  return p;
}

ll term(int &i) {
  ll p = fact(i);
  while(s[i]=='*') {
    i++;
    p *= fact(i);
  }
  return p;
}

ll exp2(int &i) {
  ll p = fact(i);
  while(s[i]=='+' || s[i]=='-' || s[i]=='*') {
    char c = s[i++];
    if (c == '+') {
      ll a = fact(i);
      p += a;
    }
    else if (c == '-') p -= fact(i);
    else {
      p *= fact(i);
    }
  }
  return p;
}

ll fact(int &i) {
  if (s[i] == '(') {
    i++;
    int p = exp(i);
    assert(s[i++]==')');
    return p;
  } else {
    int num = 0;
    while(isdigit(s[i])) {
      num *= 10;
      num += s[i]-'0';
      i++;
    }
    return num;
  }
}


int main() {
  while(cin >> s) {
    ll x;
    cin >> x;
    int i = 0;
    ll ans1 = exp(i);
    i = 0;
    ll ans2 = exp2(i);
    // cout << ans1 << " " << ans2 << endl;
    char ans;
    if (ans1 == x && ans2 == x) {
      ans = 'U';
    } else if (ans1 == x) {
      ans = 'M';
    } else if (ans2 == x) {
      ans = 'L';
    } else {
      ans = 'I';
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 1156
n, k = map(int, input().split())
mod = 10 ** 9 + 7

fact = [1] * (n + 1)
for i in range(2, n + 1):
  fact[i] = fact[i-1] * i % mod
inv_fact = [1] * (n + 1)
inv_fact[n] = pow(fact[n], mod - 2, mod)
for i in range(n - 1, 1, -1):
  inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod

def comb(_n: int, _k: int) -> int:
  return fact[_n] * inv_fact[_n - _k] * inv_fact[_k] % mod

for i in range(1, k + 1):
  red = n - k
  if i > red + 1:
    print(0)
  else:
    print(comb(red + 1, i) * comb(k - 1, k - i) % mod)

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

int N,W;
int N_MAX = 100; int W_MAX = 100000;
vector<int> w(N_MAX),v(N_MAX);
vector<vector<long long>> dp(N_MAX + 1,vector<long long>(W_MAX,0));

int main(){
    cin >> N >> W;
    for(int i = 0;i < N;i++) cin >> w[i] >> v[i];
    for(int i = 0;i < N;i++){
        for(int j = 0;j <= W;j++){
            if(j < w[i])
                dp[i+1][j] = dp[i][j];
            else 
                dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]] + v[i]);
        }
    }
    cout << dp[N][W] << endl;
}


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

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


using namespace std;
using lint = long long;

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

    int cnt = 0;
    while(N > 0){
        N /= K;
        cnt++;
    }
    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 256
N, X, M = map(int, input().split())
A = [X]
S = set()

for i in range(3 * 10 ** 6):
    nx = (A[-1]** 2) % M
    if nx in S:
        break
    S.add(nx)
    A.append(nx)

L = []
R = []
for i, a in enumerate(A):
    if a != nx:
        L.append(a)
    else:
        R = A[i:]
        break

ans = sum(L)
N -= len(L)

RS = sum(R)
ans += RS * (N // len(R))
if R:
    for i in range(N % len(R)):
        ans += R[i]

print(ans)


Measured memory_bytes: 77424
import sys
import numpy as np
# from decimal import Decimal
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

l, r, d = map(int, readline().split())
if (l % d == 0):
    print(r // d - l // d + 1)
else:
    print(r // d - l // d)


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

int main() {
  int n, p = 0, ans = 0, h;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> h;
    if (h > p) ans += h - p;
    p = h;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
//                                      KiSmAt
#include "bits/stdc++.h"
using namespace std;
 
using ll = long long;
 
const ll inf = 1e18;
const int mod = 1e9 + 7;
const int N = 2 * 1e5 + 10;

ll n;
ll res;
ll a[30][30];
ll dp[22][1LL << 22];

ll go(ll idx, ll mask){
    if(idx == n)    return 1;
    if(dp[idx][mask] + 1)   return dp[idx][mask];
    ll ans = 0;
    for(int i = 0; i < n; ++i){
        if(!a[idx][i] or mask & (1LL << i))   continue;
        ans = (ans + go(idx + 1, mask | (1LL << i))) % mod;
    }
    return dp[idx][mask] = ans;
}

void solve(){
    cin >> n;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            cin >> a[i][j];
        }
    }
    memset(dp, -1, sizeof dp);
    cout << go(0, 0);
}
 
int main(int argc, char const *argv[]){
    ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    ll t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}
// nEro

Measured memory_bytes: 721152
import java.util.List;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        List<City> citys = new ArrayList<>();
        int[] cityInPre = new int[n + 1];
        Arrays.fill(cityInPre, 0);
        for (int i = 0; i < m; i++) {
            City city = new City(i, sc.nextInt(), sc.nextInt());
            citys.add(city);
        }

        citys.sort((a, b) -> a.year - b.year);
        for (int i = 0; i < citys.size(); i++) {
            citys.get(i).number = cityInPre[citys.get(i).pref] + 1;
            cityInPre[citys.get(i).pref]++;
        }
        citys.sort((a, b) -> a.order - b.order);
        for (int i = 0; i < citys.size(); i++) {
            String s = "";
            for (int j = 0; j < 5 - Math.floor(Math.log10(citys.get(i).pref)); j++) {
                s = s + "0";
            }
            s = s + Integer.toString(citys.get(i).pref);
            for (int j = 0; j < 5 - Math.floor(Math.log10(citys.get(i).number)); j++) {
                s = s + "0";

            }
            s = s + Integer.toString(citys.get(i).number);
            System.out.println(s);
        }
    }

}

class City {
    int order;
    int pref;
    int year;
    int number;

    City(int order, int pref, int year) {
        this.order = order;
        this.pref = pref;
        this.year = year;
    }
}

Measured memory_bytes: 117348
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
using namespace std;
#define fors(i,a,b) for(int i=(a);i<=(b);++i)
#define ford(i,a,b) for(int i=(a);i>=(b);--i)
#define min(x,y) ((x) < (y) ? (x) : (y))
#define max(x,y) ((x) < (y) ? (y) : (x))
#define swap(x,y) ((x)^=(y),(y)^=(x),(x)^=(y))
const int maxn=1e6+7;
typedef long long ll;
const int inf=1<<25;
int read(){
    int s=0,f=1;
    char c=getchar();
    while(c<'0' || c>'9') {if(c=='-') f=-1; c=getchar();}
    while(c>='0' && c<='9') {s=s*10+c-48;c=getchar();}
    return s*f;
}
void write(int x){
    if(x<0) {putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+48);
}
 
int abs(int x){
    return x < 0 ? -x : x; 
}
string s;
int main(int argc, char const *argv[])
{
    
    cin>>s;
    int len=s.length();
    int flag=1;
 
    if(s[0] != '1' || s[len-1] != '0') flag=0;
 
    int r=len-2;
    fors(i,0,r){
        if(s[i]!=s[r-i]) flag=0;
    }
    if(!flag) {
        puts("-1");
    }
    else {
        int x=1;
        fors(i,0,len-2){
            write(x),putchar(' '),write(i+2),putchar(10);
            if(s[i] == '1' ) x=i+2;
         }
    }
    return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define endl '\n'
#define PI acos(-1)
typedef long long ll;
//  Table is the complete reverse of dp
//  Always think of the pattern (LCM, GCD)
//  Be careful of unsigned
//  double epsilon = FLT_EPSILON;
//	Think of a solution that gets TLE and optimize it
int n, k, *x;
char *dp[2];
bool solve(bool turn = 0, int rem = k)
{
	if(rem < x[0])
		return dp[turn][rem] = !turn;
	char &ret = dp[turn][rem];
	if(~ret)
		return ret;
	int ans = 0;
	for(int i = 0; rem >= x[i] && i < n; i++)
		if(solve(!turn, rem - x[i]) == turn)
		{
			ans = i;
			break;
		}
	return ret = solve(!turn, rem - x[ans]);
}
int main()
{
    cin.tie(nullptr); cout.tie(nullptr); ios_base::sync_with_stdio(false);
    cin >> n >> k;
    x = new int[n];
    for(int i = 0; i < 2; i++)
    {
    	dp[i] = new char[k + 1];
    	memset(dp[i], -1, k + 1);
    }
    for(int i = 0; i < n; i++)
    	cin >> x[i];
    cout << (solve()? "Second": "First");
}


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

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int maxi = 0;

    for(int i = 1; i < n; i++) {
        string t = s.substr(0, i);
        string u = s.substr(i, n-i);
        int cnt = 0;

        int l[26] = {};
        int r[26] = {};
        rep(i, t.size()) {
            l[t[i]-'a']++;
        }
        rep(i, u.size()) {
            r[u[i]-'a']++;
        }

        rep(i, 26) {
            if(r[i]>0 && l[i]>0) cnt++;
        }

        maxi = max(cnt, maxi);
    }

    cout << maxi << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int main(){
  int n;
  cin>>n;
  ll a[n+1]={};
  vector<ll> v;
  map<ll,ll> mp;
  for(int i=0;i<n;i++){
    cin>>a[i];
    v.push_back(a[i]);
  }

  sort(v.begin(),v.end());
  for(int i=0;i<n;i++){
    mp[v[i]]=i;
  }

  ll ans=0;
  for(int i=0;i<n;i++){
    if(mp[a[i]]%2){
      if(i%2==0) ans++;
    }else{
      if(i%2==1) ans++;
    }
  }

  cout<<(ans+1)/2<<endl;

  return 0;
}


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

int N, A[20], x[20][20], y[20][20], ans;

int main() {
    cin >> N;
    rep(i, N) {
        cin >> A[i];
        rep(j, A[i]) {
            cin >> x[i][j] >> y[i][j];
            x[i][j]--;
        }
    }
    for (int bit = 0; bit < (1 << N); bit++) {
        bool flag = true;
        int cnt = 0;
        rep(i, N) {
            if (bit & (1 << i)) {
                cnt++;
                rep(j, A[i]) {
                    if (((bit >> x[i][j]) & 1) ^ y[i][j]) flag = false;
                }
            }
        }
        if (flag) ans = max(ans, cnt);
    }
    cout << ans << endl;

}

Measured memory_bytes: 256
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))



import fractions

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

N = one_int()

temp = one_int()
for i in range(N-1):
    temp = lcm(temp, one_int())

print(temp)

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

#define int long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x) cout << #x << " = " << (x) << endl;
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define SP << " " <<

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
typedef vector<int> vec;
typedef vector<P> pvec;
typedef vector<vector<int>> vvec;
typedef vector<vector<P>> pvvec;
typedef priority_queue<int> PQI;
typedef priority_queue<P> PQP;
typedef priority_queue<int,vector<int>,greater<int>> PQIG;
typedef priority_queue<P,vector<P>,greater<P>> PQPG;

const vector<int> DX = {0, -1, 0, 1, 1, 1, -1, -1};
const vector<int> DY = {1, 0, -1, 0, 1, -1, 1, -1};
constexpr int MOD = (1000000007);
// const int MOD = (998244353);
// const int INF = (1 << 30); // 1073741824
const ll INF = (1LL << 60); // 1152921504606846976
const double PI = (3.141592653589794);
const double EPS = (0.0000000001); // 10^(-10)

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}
template<class T> inline T ceil(T a, T b) {return T((a + b - 1) / b);}
template<class T> inline T round(T a, T b) {return T(a / b);}
template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; }
template <class T> inline void out(T &a) { bool flag=true; for(auto&x:a){if(flag) {flag=false;} else{ cout << ' '; } cout<<x; } cout << endl; }



//----------------------------------------------------------------
int nmax=200000; // 2*(10^5)
vvec G(nmax);





void solve4ts()
{
    
    double x=1000000000000000000;
    int n;
    cin>>n;
    vector<double> a(n);
    rep(i,n) cin >> a[i];
    int ng=0;
    rep(i,n){
        if(a[i]==0) ng++;
    }
    if(ng>0){
        cout<<0<<endl;
        return;
    }
    ng=0;
    int memo=1;
    rep(i,n){
        if((double)memo>x/a[i]){
            cout<<-1<<endl;
            return;
        }
        memo*=(int)a[i];
    }
    if(memo>1000000000000000000) cout<<-1<<endl;
    else cout<<memo<<endl;
}
//-----------------------------------------------------------------

signed main(){ ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(15);
    int repeat = 1;
    // cin >> repeat;
    while(repeat--) solve4ts();
}

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

/* 10^p % 13 */
long tenpowmod13(long p) {
    if (p == 0)
        return 1;
    if (p == 1)
        return 10;
    if (p % 2 == 0) {
        long tmp = tenpowmod13(p/2);
        return tmp * tmp % 13;
    } else {
        long tmp = tenpowmod13((p-1)/2);
        return (tmp * tmp * 10) % 13;
    }
}

int main()
{
    string s;
    cin >> s;
    long mod = 1000 * 1000 * 1000+ 7;

    int len = s.length();

    vector<long> nr_m13(13);
    if (s[len - 1] == '?') {
        for (int i = 0; i < 10; i++) {
            nr_m13[i] = 1;
        }
    } else {
        int n = s[len - 1] - '0';
        nr_m13[n] = 1;
    }

    for (int i = len - 2; i >= 0; i--) {
        vector<long> tmp(13);
        vector<long> sum(13);
        if (s[i] == '?') {
            long tpm13 = tenpowmod13(len - i - 1);
            for (int j = 1; j < 10; j++) {
                long n = (tpm13 * j) % 13;
                for (int k = 0; k < 13; k++) {
                    tmp[(k + n) % 13] = nr_m13[k];
                }
                for (int k = 0; k < 13; k++) {
                    sum[k] +=tmp[k];
                    sum[k] %= mod;
                }
            }
            for (int k = 0; k < 13; k++) {
                nr_m13[k] += sum[k];
                nr_m13[k] %= mod;
            }
        } else {
            int n = s[i] - '0';
            n = tenpowmod13(len - i - 1) * n % 13;
            for (int j = 0; j < 13; j++) {
                tmp[(j + n) % 13] = nr_m13[j];
            }
            nr_m13 = tmp;
        }
    }
    cout << nr_m13[5] << endl;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define LL long long
#define REP(i,n) for(int i=0;i<(n);++i)
#define PER(i,n) for(int i=n-1;i>=0;--i)
#define REPA(i,n) for(int i=1;i<(n);++i)
#define foreach(i, n) for(auto &i:(n))
#define PII pair<int,int>
#define PLI pair<long long, int>
#define PLL pair<long long, long long>
#define MOD ((int)1e9 + 7)
#define INF ((int)1e9+5)
#define INFLL ((LL)4e18)
#define ALL(x) (x).begin(),(x).end()
#define BIT(x) (1LL << (x))
using namespace std;

int main(){
	string str;
	cin>>str;
	int N = str.size();
	vector<int>line(N);
	REP(i, N){
		if('A'<=str[i]&&str[i]<='C')line[i]=str[i]-'A';
		else line[i]=3;
	}
	vector<vector<LL>> dp(N+1, vector<LL>(4, 0));
	dp[N][3]=1;
	PER(i, N){
		if(line[i]==3)dp[i][3]=3*dp[i+1][3]%MOD;
		else dp[i][3]=dp[i+1][3];
	}
	PER(i, N){
		PER(j, 3){
			if(line[i]==3){
				dp[i][j]=dp[i+1][j+1]+3*dp[i+1][j];
			}else if(line[i]==j){
				dp[i][j]=dp[i+1][j]+dp[i+1][j+1];
			}else{
				dp[i][j]=dp[i+1][j];
			}
			dp[i][j]%=MOD;
		}
	}
	cout<<dp[0][0]<<endl;
	return 0;
}


Measured memory_bytes: 7808
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int n1 = sc.nextInt();
        int[] array1 = new int[n1];
        int i;

        for(i=0;i<n1;i++){
            array1[i] = sc.nextInt();
        }

        int n2 = sc.nextInt();
        int[] array2 = new int[n2];
        int j;

        for(j=0;j<n2;j++){
            array2[j] = sc.nextInt();
        }

        int testdata,count,sum=0,position,start,end;

        for(j=0;j<n2;j++){
            testdata = array2[j];
            count=n1;
            start = 0;
            end = n1-1;
            position=(start+end)/2;

            while(count>0){
                if(array1[position]==testdata){
                    sum += 1;
                    break;
                }else{
                    if(array1[position]>testdata){
                        end=position-1;
                    }else{
                        start=position+1;
                    }
                position=(start+end)/2;
                count/=2;
                }
            }

        }

        System.out.printf("%d\n",sum);

    }
}



Measured memory_bytes: 69260
#include <cstdio>

constexpr int maxv = 1000000000;

struct Point {
    int pta = 0, cost = 0;
    bool checked = false, vis = false;
} pt[100005];

struct Path {
    int next = 0, end = 0, weight = 0;
} ph[800005];

int n, m, e;

void set_path(int u, int v, int c) {
    ph[++e].next = pt[u].pta;
    ph[e].weight = c;
    ph[e].end = v;
    pt[u].pta = e;
}

bool dfs(int p) {
    pt[p].vis = true, pt[p].checked = true;
    for(int i = pt[p].pta; i; i = ph[i].next) {
        int s = ph[i].end;
        if(pt[s].cost > pt[p].cost + ph[i].weight) {
            pt[s].cost = pt[p].cost + ph[i].weight;
            if(pt[s].vis || !dfs(s))
                return false;
        }
    }
    pt[p].vis = false;
    return true;
}

bool check() {
    for(int i = 1; i <= n; ++i)
        if(!pt[i].checked && !dfs(i))
            return false;
    return true;
}

int main() {
    std::scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; ++i) {
        int u, v, c;
        std::scanf("%d %d %d", &u, &v, &c);
        set_path(u, v, c);
        set_path(v, u, -c);
    }
    for(int i = 1; i <= n; ++i)
        set_path(0, i, maxv);
    std::puts(check() ? "Yes" : "No");
    return 0;
}

Measured memory_bytes: 10496
package main

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

func main() {
	K, A, B := ReadInt(), ReadInt(), ReadInt()
	if B-A-2 <= 0 {
		fmt.Println(1 + K)
		return
	}
	t := (K - A + 1) / 2
	if t <= 0 {
		fmt.Println(1 + K)
		return
	}
	fmt.Println(1 + t*(B-A) + (K - 2*t))
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


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

ans = 0
tmp = 0

for i in range(1, N):
    if H[i - 1] >= H[i]:
        tmp += 1
    else:
        ans = max(ans, tmp)
        tmp = 0

ans = max(ans, tmp)

print(ans)


Measured memory_bytes: 14252
class SegmentTree:
    def __init__(self, N, mode=min):
        n_ = 1
        
        while n_ < N:
            n_ *= 2
            
        self.n = n_
        self.mode = mode
        
        if self.mode == min:
            self.arr = [2**31-1] * (2*self.n - 1)
        elif self.mode == max:
            self.arr = [-2**31+1] * (2*self.n - 1)
    
    def update(self, k, a):
        k += self.n - 1
        self.arr[k] = a
        
        while k > 0:
            k = (k - 1) // 2
            self.arr[k] = self.mode(self.arr[2*k+1], self.arr[2*k+2])
    
    def query(self, l, r):
        L, R = l + self.n, r + self.n
        
        if self.mode == min:
            res = 2**31-1
        else:
            res = -2**31+1
        
        while L < R:
            if R & 1:
                R -= 1
                res = self.mode(res, self.arr[R-1])
            
            if L & 1:
                res = self.mode(res, self.arr[L-1])
                L += 1
            
            L >>= 1
            R >>= 1
        
        return res

n, q = map(int, input().split())
st = SegmentTree(n, min)

for _ in range(q):
    com_i, xi, yi = map(int, input().split())
    
    if com_i == 0:
        st.update(xi, yi)
    else:
        print(st.query(xi, yi+1))


Measured memory_bytes: 8692
// https://atcoder.jp/contests/abc061/tasks/abc061_d
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()

template <typename T> struct edge {
    int src, to;
    T cost;

    edge(int to, T cost) : src(-1), to(to), cost(cost) {}

    edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

    edge &operator=(const int &x) {
        to = x;
        return *this;
    }

    operator int() const { return to; }
};

template <typename T> using Edges = vector<edge<T>>;
template <typename T> using WeightedGraph = vector<Edges<T>>;
using UnWeightedGraph = vector<vector<int>>;
template <typename T> using Matrix = vector<vector<T>>;

template <typename T> vector<T> bellman_ford(Edges<T> &edges, int V, int s) {
    const auto INF = numeric_limits<T>::max();
    vector<T> dist(V, INF);
    dist[s] = 0;
    for (int i = 0; i < V; i++) {
        for (auto &e : edges) {
            if (dist[e.src] == INF)
                continue;
            if (dist[e.to] > dist[e.src] + e.cost) {
                dist[e.to] = dist[e.src] + e.cost;
                // 一番離れた頂点間はN-1なので、N回目のループでコストが小さくなったら負閉路がある
                // 後者の条件は通常のベルマンフォード法では不要だが、今回は頂点Nのスコアに影響する負閉路のみを検出する
                if (i == V - 1 && e.to == V - 1) {
                    return vector<T>();
                }
            }
        }
    }
    return dist;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, M;
    cin >> N >> M;
    Edges<ll> es;
    REP(i, M) {
        int a, b, c;
        cin >> a >> b >> c;
        es.emplace_back(a - 1, b - 1, -c);
    }
    auto dists = bellman_ford(es, N, 0);
    if (dists.size() == 0) {
        cout << "inf\n";
    } else {
        cout << -dists.back() << "\n";
    }

    return 0;
}


Measured memory_bytes: 384