akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<string>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<bitset>
#include<functional>
#include<climits>
using namespace std;
typedef pair<int,int>pii;
const int INF=1e9;
const int dx[]={0,-1,0,1},dy[]={-1,0,1,0};


int main(){
    int n;
    while(cin>>n,n){
        int a[100];for(int i=0;i<n;i++)cin>>a[i];
        char str[128];cin>>str;
        for(int i=0;str[i];i++){
            int val=(isupper(str[i])?tolower(str[i])-'a'+26:str[i]-'a');
            int next=val-a[i%n];
            next=(next+52)%52;
            if(next>25)next=toupper('a'+next-26)-'a';
            printf("%c",'a'+next);
        }
        puts("");
    }
    return 0;
}

Measured memory_bytes: 1124
import java.util.*;


public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();

        long sum = 0;
        if((a+b)/2 >= c){
            if(x == y){
                sum = x * 2 *c;
            } else if (x > y) {
                sum += y * 2*c;
                x = x-y;
                if(a > c * 2){
                    sum += x * 2 * c;
                }else{
                    sum += x*a;
                }
            }else{
                sum += x * 2 *c;
                y = y-x;
                if(b > c*2){
                    sum += y * 2* c;
                }else{
                    sum += y*b;
                }
            }
        }else{
            sum = a*x + b*y;
        }
        System.out.println(sum);

    }
}

Measured memory_bytes: 21972
#include <iostream>
#include <math.h>
#include <iomanip>

using namespace std;
int main() {
    double a, b, c, d;
    cin >> a >> b >> c >>d;
    double x = (a - c)*(a - c);
    double y = (b - d) *(b - d);

    cout << fixed << setprecision(10) << sqrt(x + y) << endl;

    return 0;
}


Measured memory_bytes: 3288
n = int(input())
g = [None] * n
visited = [0] * n
root = set(range(n))
ts = [[0, 0] for _ in range(n)]
t = 0

while n:
    l = list(map(int, input().split()))
    connected = [i - 1 for i in l[2:]]
    g[l[0] - 1] = [i - 1 for i in l[2:]]
    root -= set(connected)
    n -= 1


def dfs(i):
    global g, t, ts, visited
    lts = ts[i]
    t += 1
    lts[0] = t
    visited[i] = 1
    for c in g[i]:
        if not visited[c]:
            dfs(c)
    t += 1
    lts[1] = t

if root:
    for r in sorted(root):
        dfs(r)
else:
    dfs(0)

for i, v in enumerate(ts):
    print(i + 1, *v)

Measured memory_bytes: 7800
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip> 
#include <bits/stdc++.h>
using namespace std;
double pi=3.14159265358979323846264338;
#include <bits/stdc++.h>

#ifndef LOCAL
#define cerr dolor_sit_amet
#endif

#define mp make_pair
#define sz(x) ((int)((x).size()))
#define X first
#define Y second
#define all(x) (x).begin(), (x).end()

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < int , int > ipair;
typedef pair < ll , ll > lpair;
const int IINF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;
const double DINF = numeric_limits<double>::infinity();
const int MOD = 1000000007;
const double EPS = 1e-9;
const double PI = acos(-1.0);
const int DX[] = { 1,  0, -1,  0,  1, -1,  1, -1};
const int DY[] = { 0,  1,  0, -1,  1, -1, -1,  1};

template<typename T> T& updMin(T& a, T const& b) { if (b < a) a = b; return a; }
template<typename T> T& updMax(T& a, T const& b) { if (a < b) a = b; return a; }

// ========================================================================= //
//999977 17 499998
const int ind=6000000;
double h,c,t;
double tem(double cur){
	if((2*cur+3)*labs(t*(2*cur+1)-(cur*(h+c)+h))>(2*cur+1)*fabs(t*(2*cur+3)-((cur+1)*(h+c)+h))){
		return (2*cur+3);
	
	}else {
		if((2*cur-1)*labs(t*(2*cur+1)-(cur*(h+c)+h))<(2*cur+1)*fabs(t*(2*cur-1)-((cur-1)*(h+c)+h))){
			return(2*cur+1);
			//cout<<fabs(t-(cur*(h+c)+h)/(2*cur+1))<<" "<<fabs(t-((cur-1)*(h+c)+h)/(2*cur-1))<<endl;
		}else {
			//cout<<fabs(t-(cur*(h+c)+h)/(2*cur+1))<<" "<<fabs(t-((cur-1)*(h+c)+h)/(2*cur-1))<<endl;
			return (2*cur-1);
			
		}
	}
}
long long culc(){
	long long fr=0;
	long long ls=ind;
	long long mid;
	while(ls>=fr){
		mid=(fr+ls)/2;
		if ((mid*(h+c)+h)/(2*mid+1)<t)ls=mid-1; else if((mid*(h+c)+h)/(2*mid+1)>t)fr=mid+1; else return mid;
	}
	return mid;
}



int main() {
	
	string s;
	cin>>s;
	int lnth=s.length();
	for(int i=0;i<lnth;i++){
		if(s[i]=='?')s[i]='D';
	}
	cout<<s<<endl;
  return 0;
}


Measured memory_bytes: 3724
#include<stdio.h>
int main(void)
{
	int E, Y;
	scanf("%d %d", &E, &Y);
	if (E == 0)
	{
		if (Y <= 1911)
		{
			printf("M%d\n", Y - 1867);
		}
		else if (Y <= 1925)
		{
			printf("T%d\n", Y - 1911);
		}
		else if (Y <= 1988)
		{
			printf("S%d\n", Y - 1925);
		}
		else
		{
			printf("H%d\n", Y - 1988);
		}
	}
	else if (E == 1)
		printf("%d\n", Y + 1867);
	else if (E == 2)
		printf("%d\n", Y + 1911);
	else if (E == 3)
		printf("%d\n", Y + 1925);
	else if(E==4)
	printf("%d\n", Y + 1988);
		return 0;
}

Measured memory_bytes: 596
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<utility>
#include<vector>
#include<queue>
#include<deque>

#define rep(i, a, n)  for(int i=a; i<n; i++)
#define per(i, a, n)  for(int i=n-1; i>=a; i--)
#define fill0(n)  setfill('0') << right << setw(n)
#define all(x)  (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define MAX 1000001
using namespace std;
typedef long long ll;

int n;
int m;
int a[40];
int b[40];
bool graph[40][40];


int dfs(int x, bool visited[9]){
  bool all_visited=true;
  rep(i,1,n+1){
    if (!visited[i]) all_visited=false;
  }
  if(all_visited)return 1;

  //次の頂点のお話
  int res=0;

  rep(i,1,n+1){
    if(graph[x][i] && !visited[i]){
      visited[i] = true;
      res += dfs(i,visited);
      visited[i] = false;
    }
  }
  return res;
}

int main(){
  std::cin >> n >> m;
  rep(i,1,m+1){
    std::cin >> a[i]>>b[i];
    graph[a[i]][b[i]] = true;
    graph[b[i]][a[i]] = true;
  }
  bool visited[9];
  rep(i,1,n+1){
    visited[i] = false;
  }
  visited[1] = true;
  int ans = dfs(1, visited);
  std::cout << ans << '\n';

}


Measured memory_bytes: 256
import sys
import numpy as np
sys.setrecursionlimit(10**8)

def dfs(i,a,value):
  global ans
  if i==n:
    if all(a[i]>=x for i in range(m)):
      ans=min(ans,value)


  else:
    dfs(i+1,a,value)
    dfs(i+1,a+np.array(pc[i][1:]),value+pc[i][0])


ans=float('inf')
n,m,x=map(int,input().split())
pc=[]
for i in range(n):
  s=list(map(int,input().split()))
  pc.append(s)

dfs(0,np.array([0]*(m)),0)
if ans==float('inf'):
  ans=-1
print(ans)


Measured memory_bytes: 27256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())
#define FORV(i, v) for (auto i = v.begin(); i != v.end(); i++)
using namespace std;

using ll = long long;
using P = pair<int, int>;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline void dump(vector<T> v) { for (auto& x : v) cerr << x << " "; cerr << endl; }
template<class T> inline void dump(vector<pair<T, T>> v) { for (auto& p : v) cerr << p.first << " " << p.second << endl; }
template<class T> inline void dump(vector<vector<T>> vv) { for (auto& v : vv) {for (auto& x : v) cerr << x << " "; cerr << endl;} }

const ll INF = 1e9;
const long long INFL = 1LL<<60;

const double PI = acos(-1);

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

  k -= a - 1;
  ll ans = a;

  ans += (k / 2) * (b - a);
  ans += k % 2;

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3580
import re

patterns = [
  r'^.*keyence$',
  r'^k.*eyence$',
  r'^ke.*yence$',
  r'^key.*ence$',
  r'^keye.*nce$',
  r'^keyen.*ce$',
  r'^keyenc.*e$',
  r'^keyence.*$',
]

def solve(S):
  for pattern in patterns:
    if re.match(pattern, S):
      return 'YES'
  return 'NO'

S = input()

print(solve(S))

Measured memory_bytes: 3316
#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<iomanip>
#include<set>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define brep(index,num) for(int index=num-1;index>=0;index--)
#define brep1(index,num) for(int index=num;index>0;index--)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef long long ll;
typedef long double ld;
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(){
	int N,M;
	string S;
	scan(N>>M>>S);
	int flag=1;
	int now=0;
	rep(i,N){
		if(S[i]=='1') now++;
		else now=0;
		if(now>=M) flag=0;
	}
	if(flag){
		if(M>=N){
			prin(N);
			return 0;
		}
		int dp[100002];
		fill(dp,dp+N+1,N+1);
		int num[100002]={};
		int nummin=0;
		dp[N]=0;
		num[0]++;
		for(int i=N-1;i>=N-M;i--){
			if(S[i]=='0') dp[i]=1;
			num[dp[i]]++;
		}
		for(int i=N-M-1;i>=0;i--){
			num[dp[i+M+1]]--;
			if(dp[i+M+1]==nummin&&num[dp[i+M+1]]==0){
				nummin++;
			}
			if(S[i]=='0'){
				dp[i]=nummin+1;
			}
			num[dp[i]]++;
		}
		bool alre[100002]={};
		int lastmasu=0;
		/*rep(i,N+1){
			printf("%d ",dp[i]);
		}
		kaigyo;*/
		alre[dp[0]]=1;
		rep1(i,N){
			if(i==N){
				printf("%d ",i-lastmasu);
				kaigyo;
				return 0;
			}
			if(dp[i]<=N&&alre[dp[i]]==0){
				alre[dp[i]]=1;
				printf("%d ",i-lastmasu);
				lastmasu=i;
			}
		}
	}
	else{
		prin(-1);
	}
	return 0;
}


Measured memory_bytes: 1536
#include<stdio.h>
int main()
{
    int e,y;
    scanf("%d %d",&e,&y);
    if(e==0){
        if(y>=1989 && y<=2016){
            printf("H%d\n",y-1988);
        }else if(y>=1926 && y<=1988){
            printf("S%d\n",y-1925);
        }else if(y>=1912 && y<=1925){
            printf("T%d\n",y-1911);
        }else if(y>=1868 && y<=1911){
            printf("M%d\n",y-1867);
        }
    }else if(e==1){
        printf("%d\n",y+1867);
    }else if(e==2){
        printf("%d\n",y+1911);
    }else if(e==3){
        printf("%d\n",y+1925);
    }else if(e==4){
        printf("%d\n",y+1988);
    }
    return 0;
}


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

#define task "D"
#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define Rep(i, r, l) for (int i = (r); i >= (l); --i)
#define pb push_back
#define F first
#define S second
#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; } // sort(arr, arr + N, by(a));

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using namespace std;

typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vl;

// Limit

// Struct

// Variables
int n,a[100005];
long long s=0,s1,m;
// Function

int main()
{
	//freopen(task".in","r",stdin);
	//freopen(task".out","w",stdout);
	ios_base::sync_with_stdio(false);cin.tie(nullptr);
	cin >> n;
	rep(i,1,n)
	{
	    cin >> a[i];
	    if (i%2==0) s1+=a[i];
	    s+=a[i];
	}
	m=s-2*s1;
	//cout << s << '\n';
	rep(i,1,n)
	{
	    cout << m << ' ';
	    m=2*a[i]-m;
	}
}


Measured memory_bytes: 1664
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define MOD 1000000007
using namespace std;

typedef pair<int, int> P;
typedef pair<long long, long long> LLP;

long long sum[4][4][4];

bool check4(int i, int j, int k, int l) {
    if (j == 0 && k == 2 && l == 1) return false;
    if (j == 2 && k == 0 && l == 1) return false;
    if (j == 0 && k == 1 && l == 2) return false;
    if (i == 0 && k == 2 && l == 1) return false;
    if (i == 0 && j == 2 && l == 1) return false;
    return true;
}

bool check3(int i, int j, int k) {
    if (i == 0 && j == 2 && k == 1) return false;
    if (i == 0 && j == 1 && k == 2) return false;
    if (i == 2 && j == 0 && k == 1) return false;
    return true;
}

void mul() {
    long long before[4][4][4];
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            for (int k = 0; k < 4; k++) {
                before[i][j][k] = sum[i][j][k];
            }
        }
    }
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            for (int k = 0; k < 4; k++) {
                sum[i][j][k] = 0;
            }
        }
    }
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            for (int k = 0; k < 4; k++) {
                for (int l = 0; l < 4; l++) {
                    if (check4(i, j, k, l)) sum[j][k][l] = (before[i][j][k] + sum[j][k][l]) % MOD;
                }
            }
        }
    }
}

int main() {
    int N;
    cin >> N;
    if (N == 3) {
        cout << 61 << endl;
        return 0;
    }
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            for (int k = 0; k < 4; k++) {
                sum[i][j][k] = check3(i, j, k) ? 1 : 0;
            }
        }
    }
    for (int i = 4; i <= N; i++) {
        mul();
    }
    long long ans = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            for (int k = 0; k < 4; k++) {
                ans = (ans + sum[i][j][k]) % MOD;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>

long long calc(int n, std::vector<int>& as, std::vector<int>& bs, std::vector<int>& cs) {
  std::sort(as.begin(), as.end());
  std::sort(bs.begin(), bs.end());
  std::sort(cs.begin(), cs.end());

  long long ans = 0LL;
  int j = n - 1;
  int k = n - 1;
  long long prev1 = 0LL;
  long long c = 0LL;
  int c_k = 0;

  for(int i = n - 1; 0 <= i; i--) {
    c = 0LL;
    for(; 0 <= j && as[i] < bs[j]; j--) {
      for(; 0 <= k && bs[j] < cs[k]; k--) {
        c_k++;
      }
      c += c_k;
    }
    ans += prev1 + c;
    prev1 += c;
  }

  return ans;
}

int main(){
  int n;
  std::cin >> n;
  std::vector<int> as(n);
  std::vector<int> bs(n);
  std::vector<int> cs(n);

  for(int i = 0; i < n; i++)
    std::cin >> as[i];
  for(int i = 0; i < n; i++)
    std::cin >> bs[i];
  for(int i = 0; i < n; i++)
    std::cin >> cs[i];

  std::cout << calc(n, as, bs, cs) << "\n";
}


Measured memory_bytes: 1408
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

suma = [0 for i in range(len(a)+1)]
sumb = [0 for i in range(len(b)+1)]

for i in range(1, len(a)+1):
    suma[i] = suma[i-1] + a[i-1]

for i in range(1, len(b)+1):
    sumb[i] = sumb[i-1] + b[i-1]

mnum = 0
best = len(sumb)
for i in range(len(suma)):
    for j in range(best)[::-1]:
        if suma[i] + sumb[j] <= k:
            mnum = max(mnum, i+j)
            best = j+1
            break

print(mnum)

Measured memory_bytes: 47436
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define DEBUG true
#ifdef ONLINE_JUDGE
#undef DEBUG
#define DEBUG false
#endif 

using namespace std;

#define MAXN ((ll)2e5+5)
#define MOD ((ll)1e9 + 7)
#define INF ((ll)1e9 + 9)
#define ll long long
#define _ << " " <<
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define TRACE(x) if(DEBUG) cerr << #x << " = " << x << endl;
#define TRACE2(x,y) if(DEBUG) cerr << #x << " = " << x << " | " << #y << " = " << y << endl;
#define pb push_back
#define all(x) x.begin(), x.end()
#define endl "\n"
#define pii pair<ll,ll>
#define mid ((l+r)/2)

string s;
ll k,n;
ll ans;

map <int,int> mp;

ll f(string a)
{
	ll ct = 0 ;
	ll n_ = a.size();
	for (ll i = 1; i < n_; ++i)
	{
		if(a[i] == a[i-1])
		{
			a[i] = '#';
			ct++;
		}
	}
	return ct;
}

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin >> s >> k;
	n = s.size();

	for (int i = 0; i < n; ++i)
		mp[s[i]]++;

	if(mp.size() == 1)
		ans = (k * n) / 2; 
	else
	{
		ll l = 0, r = 0;
		while(s[l] == s[l+1]) l++;
		while(s[n-1-r] == s[n-2-r]) r++;

		l++;
		r++;

		TRACE2(l,r);

		ans = l / 2 + r / 2;

		if(s[0] == s[n-1])
			ans += (k-1) * ((l+r)/2);
		else
			ans += (k-1) * (l/2 + r/2);

		string tmp;
		for (int i = l; i < n-r; ++i)
			tmp += s[i];

		TRACE2(tmp,f(tmp));
		
		ans += f(tmp) * k;
	}

	cout << fixed << ans << endl;
}

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

typedef long long ll;

const ll MOD = 1e9 + 7;

int main() {
    string S;
    cin >> S;
    int i = S.size() - 1;
    while (i > 3) {
        if (S[i] == 'm') {
            if (S.substr(i - 4, 5) == "dream") {
                i -= 5;
                continue;
            }
            break;
        }
        if (S[i] == 'e') {
            if (S.substr(i - 4, 5) == "erase") {
                i -= 5;
                continue;
            }
            break;
        }
        if (i < 5) break;
        if (S[i] == 'r') {
            if (S.substr(i - 5, 6) == "eraser") {
                i -= 6;
                continue;
            }
            if (i < 6) break;
            if (S.substr(i - 6, 7) == "dreamer") {
                i -= 7;
                continue;
            }
        }
        break;
    }
    if (i == -1) cout << "YES" << endl;
    else cout << "NO" << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll k;
  string s;
  cin >> k >> s;
  if(s.size() > k) {
    cout << s.substr(0, k);
    cout << "..." << endl;
  } else
    cout << s << endl;
}

Measured memory_bytes: 3632
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <string>

using namespace std;

int C[26]{};

int main() {
  string s;
  cin >> s;
  int N = s.size();
  int t = N;
  for (int i = 0; i < 26; ++i) {
    int j = 0;
    int _t = 0;
    while (j < N) {
      int cnt = 0;
      while (j < N && s[j] == i + 'a') {
        ++j;
      }
      while (j < N && s[j] != i + 'a') {
        ++cnt;
        ++j;
      }
      _t = max(_t, cnt);
    }
    t = min(t, _t);
  }
  printf("%d\n", t);
}

Measured memory_bytes: 3208
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
	int n, m;
	scanf("%d %d", &n, &m);
	int a[n], x, y;
	fill(a, a + n, -1);
	for (int i = 0; i < m; i++){
		scanf("%d %d", &x, &y);
		if (a[x - 1] == -1 || a[x - 1] == y){
			a[x - 1] = y;
		}else{
			printf("-1\n");
			return 0;
		}
	}
	if (a[0] == -1){
		if (n == 1){
			a[0] = 0;
		}else{
			a[0] = 1;
		}
	}
	for (int i = 1; i < n; i++){
		if (a[i] == -1) a[i] = 0;
	}
	if (n == 1){
		printf("%d\n", a[0]);
		return 0;
	}else if (a[0] == 0){
		printf("-1\n");
		return 0;
	}
	for (int i = 0; i < n; i++){
		printf("%d", a[i]);
	}
}

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

#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)

int main()
{
	int N;
	int A, B;
	scanf("%d%d%d", &N,&A,&B);

	printf("%d\n",min(N * A, B));
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
using namespace std;
long long MOD = 1000000007;
int main()
{
  string S;
  cin >> S;
  vector<long long> count(13, 0LL);
  count[0] = 1LL;
  for (auto c : S)
  {
    vector<long long> nextgen(13, 0LL);
    for (int digit = 0; digit < 10; digit++)
    {
      if (c == '?' || c == digit + '0')
        for (int i = 0; i < 13; i++)
        {
          int next = (i * 10 + digit) % 13;
          nextgen[next] += count[i];
          nextgen[next] %= MOD;
        }
    }
    count = nextgen;
  }
  cout << count[5] << endl;
}

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

int gen[1000000];
int used[1000001];
int main(){
	vector<int> p;
	for(int i = 0 ; i < 1500000 ; i++) gen[i] = 1;
	gen[0] = gen[1] = 0;
	for(int i = 0 ; i*i < 1500000 ; i++){
		if(gen[i]){
			for(int j = i*i ; j < 1500000 ; j+=i)
				gen[j] = 0;
		}
	}
	for(int i = 0 ; i < 1500000 ; i++) if(gen[i])p.push_back(i);
	
	long long A,B;
	cin >> A >> B;
	
	long long X = max(2ll,A-B) , Y = A+B;
	if(Y<2){ cout << 0 << endl; return 0; }
	
	for(int i = 0 ; i <= 1000000 ; i++) used[i] = 9999999;
	
	for(int i = 0 ; i < p.size() ; i++){
		for(long long j = X+(p[i]-X%p[i])%p[i] ; j <= Y ; j += p[i]){
			//if(used[j]==-1) continue;
			long long n_ = j , ok = 0;
			while(n_%p[i]==0) ok++ , n_ /= p[i];
			if(ok){
				if(used[j-X] >= ok){
					used[j-X] = ok;
				}else{
					used[j-X] = -1;
				}
			}
			//cout << p[i] << " " << ok << " " << used[j-X] << endl;
		}
	}
	int ans = 0;
	for(int i = 0 ; i <= Y-X ; i++){
		if(used[i] != -1) ans++;
	}
	cout << ans << endl;

}

Measured memory_bytes: 9268
#include<iostream>

int main(){
    int i,j,a[4];
    a[3]=0;

    std::cin>>a[0]>>a[1]>>a[2];

    for(j=0;j<2;j++){
        for(i=0;i<2;i++){
            if(a[i]>a[i+1]){
                a[3]=a[i];
                a[i]=a[i+1];
                a[i+1]=a[3];
            }
        }
    }
    std::cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<std::endl;

    return 0;

}


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

#define rep(i, N) for (ll i = 0; i < N; i++)

using ll = long long;
using namespace std;

typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<P> vpi;

int main() {
    ll ans = 0;
    int N, M;
    cin >> N >> M;
    vi A(N);
    rep(i, N) cin >> A[i];
    vpi CB(M);
    rep(i, M) cin >> CB[i].second >> CB[i].first;

    sort(A.begin(), A.end());
    sort(CB.begin(), CB.end(), greater<P>());

    int Aindex = 0, CBindex = 0;
    rep(cnt, N) {
        if(CBindex < M && A[Aindex] < CB[CBindex].first) {
            ans += CB[CBindex].first;
            CB[CBindex].second--;
            Aindex++;
            if(CB[CBindex].second <= 0) CBindex++;
        } else {
            rep(i, N-cnt) ans += A[N-1-i];
            break;
        }
    }

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


Measured memory_bytes: 1408
#pragma region
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))

using namespace std;

using i32 = int;
using i64 = long long;
using u64 = unsigned long long;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vu64 = vector<u64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "No" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); return a / gcd(a, b) * b; }
inline u64 xorshift() { static u64 x = 88172645463325252ull; x = x ^ (x << 7); return x = x ^ (x >> 9); }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { if (x < y) x = y; }
template <typename T> inline void amin(T &x, T y) { if (x > y) x = y; }
template <typename T> inline T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> inline T bis(T ok, T ng, function<bool(T)> f, T eps = 1) { while (abs(ok - ng) > eps) { T mi = (ok + ng) / 2; (f(mi) ? ok : ng) = mi; } return ok; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }
#pragma endregion

void solve() {
  i64 ans = 0;
  int n;
  cin >> n;
  reps(i, n - 1) ans += i;
  cout << ans << endl;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    string s,t;
    cin>>s>>t;
    ll q,a,b,c,d;
    cin>>q;
    ll n=s.length(),m=t.length();
    ll x[1+n];
    ll y[1+m];
    x[0]=y[0]=0;
    for(int i=0;i<n;i++){
    	if(s[i]=='A')x[i+1]=(x[i]+1)%3;
    	else x[i+1]=(x[i]+2)%3;
    }
    for(int i=0;i<m;i++){
    	if(t[i]=='A')y[i+1]=(y[i]+1)%3;
    	else y[i+1]=(y[i]+2)%3;
    }
    vector<int> v; 
    while(q--){
    	cin>>a>>b>>c>>d;
    	if((x[b]-x[a-1]-y[d]+y[c-1])%3==0)v.pb(1);
    	else v.pb(0);
    }
    for(auto& i:v)cout<<((i)?"YES":"NO") <<endl;
    return 0;
}


Measured memory_bytes: 2888
#########行列読み込み ##############################################
"""
from sys import stdin
n = int(stdin.readline().rstrip())
data = [stdin.readline().rstrip().split() for _ in range(n)]
print(data)
print(*data, sep='\n')
"""
##################################################################
#########入力系####################################################
"""
s =input()
s=list(input())
a=int(input())
x,y = map(int,input().split())	
li = input().split()	
li = list(map(int,input().split()))	
li = input().split('T')	
"""
##################################################################

#########行列読み込み ##############################################
"""
from sys import stdin
n = int(stdin.readline().rstrip())
data = [stdin.readline().rstrip().split() for _ in range(n)]
print(data)
print(*data, sep='\n')
"""
##################################################################
#########入力系####################################################
"""
s =input()
s=list(input())
a=int(input())
x,y = map(int,input().split())	
li = input().split()	
li = list(map(int,input().split()))	
li = input().split('T')	
"""
##################################################################

a,b = map(int,input().split())	

mini = min(a,b)
maxx = max(a,b)
for i in range(maxx):
    print(mini, end="")











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

long long N, a[100000];
int bit[1000010];

void add(int a, int w){
    for(int x = a; x <= N+100001; x += x & -x) bit[x] += w;
}
int sum(int a){
    int ret = 0;
    for(int x = a; x > 0; x -= x & -x) ret += bit[x];
    return ret;
}

bool judge(int x){
    int S[100001] = {};
    for(int i = 0; i <= 200010; i++){
        bit[i] = 0;
    }
    long long cnt = 0;
    add(0+100001, 1);
    for(int i = 1; i <= N; i++){
        S[i] = S[i-1] + (a[i-1] >= x ? 1 : -1);
        cnt += sum(S[i]+100001);
        add(S[i]+100001, 1);
    }
    return cnt >= (N*(N+1)/2 + 1)/2;

}


// begin: ok, end: ng
int binary_search(int begin, int end){
    if(end - begin <= 1){
        return begin;
    }
    int mid = (begin + end) / 2;
    if(judge(mid)){
        return binary_search(mid, end);
    }else{
        return binary_search(begin, mid);
    }
}


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


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

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

map<ll,ll> decomposePrime(ll n){
    map<ll,ll> m;
    ll x = 2;
    while(x*x <= n){
        if (n%x==0){
            m[x]++;
            n /= x;
        }else{
            x++;
        }
    }
    if (n > 1)
        m[n]++;
    return m;
}

const ll MOD=1e9+7;
ll  fact[200000];
ll rfact[200000];

ll mpow(ll x, ll y, ll m) {
    if (y == 0)
        return 1;
    else if (y%2 == 1)
        return x * mpow(x, y-1, m)%m;
    else
        return mpow(x*x%m, y/2, m)%m;
}

// mod inverse 法mにおけるxの逆数
ull minverse(ull x, ull m) {
    return mpow(x, m-2, m);
}

void c3_init(ll m) {
    fact[1] = rfact[1] = 1;
    for (ll i = 2; i < 200000; i++) {
        fact[i] = (fact[i-1]*i)%m;
        rfact[i] = minverse(fact[i], m);
    }
}

ll c3(ll n, ll k, ll m) {
    if (n < k)
        return 0;
    else if (n == k || k == 0)
        return 1;
    else
        return (((fact[n] * rfact[k])%m) * rfact[n-k])%m;
}


signed main() {
    c3_init(MOD);
    ll N,M;
    cin>>N>>M;

    ll ans=1;
    auto m = decomposePrime(M);
    for (auto e: m){
        // cout<<e.first<<":"<<e.second<<endl;;
        ans *= c3(e.second+N-1,e.second,MOD);
        ans %= MOD;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

int main(){
    ll N,h,n,w;
    cin>>N;
    FOR(i,1,3501)FOR(j,1,3501){
        ll x=N*i*j,y=-N*(i+j)+4ll*i*j;
        if(y!=0&&x%y==0&&x/y>0){
            cout<<i<<" "<<j<<" "<<x/y<<endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define FIO "Digits Sum"
using namespace std;

int n , ans = 0;

inline int calc(int x)
{
	int res = 0;
	while(x)
	{
		res += x % 10;
		x /= 10;
	}
	return res;
}

int main()
{
	cin >> n; ans = 0x3f3f3f3f;
	for(int i = 1; i < n; i ++)
	{
		ans = min(ans , calc(i) + calc(n - i));
//		cerr << ans << endl;
	}
	cout << ans << endl;
	return 0;
}

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

int main() {
    char a;
    cin >> a;
    if ('a' <= a && a <= 'z') {
        cout << 'a' << endl;
    } else {
        cout << 'A' << endl;
    }
    return 0;
}


Measured memory_bytes: 3632
# coding: utf-8
dic={}
input()
for i in map(int,input().split()):
    if i in dic:
        dic[i]+=1
    else:
        dic[i]=1
input()
for i in map(int,input().split()):
    if i in dic:
        dic[i]-=1
        if dic[i]<0:
            print('NO')
            exit()
    else:
        print('NO')
        exit()
print('YES')

Measured memory_bytes: 44644
#include <queue>
#include <cstdio>
#include <iostream>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <stack>
using namespace std;
typedef long long int ll;

#define EPS (1e-9)
#define INF (1e9)
#define PI (acos(-1))
#define REP(i,n) for(int i=0;i<n;i++)

/*
int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
*/

int H, W;
int c[20][20];
int A[500][500];
ll cost[20];
bool cschk[20] = {};
ll ans = 0;

int main() {
	cin >> H >> W;
	REP(i, 10) {
		REP(j, 10) {
			cin >> c[i][j];
		}
	}
	REP(i, H) {
		REP(j, W) {
			cin >> A[i][j];
		}
	}
	REP(k, 10) {
		REP(i, 10) {
			REP(j, 10) {
				c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
			}
		}
	}
	REP(i, H) {
		REP(j, W) {
			ans += c[A[i][j]][1];
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 640
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;
using static System.Array;

class Program
{
    public static void Main()
    {
        var n = ReadLine().Split().Select(long.Parse).ToArray();
        var s = n[0];
        var c = n[1];
        var temp = c - s - s;
        if(temp > 0)
        {
            s += temp / 4;
            c -= temp / 2;
        }
            

        WriteLine(Min(s, c / 2));
    }
}


Measured memory_bytes: 18772
using System;

namespace tes
{
    class Program
    {
        public static void Main()
        {
            String str = Console.ReadLine();
            String[] num = str.Split();
            for (int i = 0; i < num.Length; i++)
            {
                for (int j = i+1; j < num.Length; j++)
                {
                    if (int.Parse(num[i]) > int.Parse(num[j]))
                    {
                        String temp = num[i];
                        num[i] = num[j];
                        num[j] = temp;
                    }
                }
            }

            for (int i = 0; i < num.Length; i++)
            {
                if (i != 0)
                {
                    Console.Write(" " + num[i]);
                }
                else
                {
                    Console.Write("" + num[i]);
                }
            }
            Console.WriteLine();
        }
    }
}

Measured memory_bytes: 5316
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define tp tuple<int,int,int>
#define mtp make_tuple
using namespace std;

const int N=1e5+5;
int h[N];
set<int>adj[N];

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>h[i];
    while(m--)
    {
        int u,v;
        cin>>u>>v;
        adj[u].insert(h[v]);
        adj[v].insert(h[u]);
    }
    int res=0;
    for(int i=1;i<=n;i++)
    {
        int val=0;
        if(!adj[i].empty()) val=*adj[i].rbegin();
        if(h[i]>val) res++;
    }
    cout<<res;
}


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

int main()
{
	int h,m,s;
	cin >> s;
	h = s / 3600;
	s -= h * 3600;
	m = s / 60;
	s -= m*60;
	cout << h << ":" << m <<":"<<s<< endl;
    return 0;
}

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

int main()
{
	array<string, 3> s;
	for (auto& i : s) {
		cin >> i;
	}
	cout << s[0][0] << s[1][1] << s[2][2] << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath>
#include <limits>
using namespace std;
using ll = long long;

int main(){
  ll a,b,c,d;
  cin >> a >> b >> c >> d;
  cout << max(max(max(a*c,b*d),a*d),b*c) << endl;
}

Measured memory_bytes: 3632
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
using namespace std;
int main()
{
    int q = 0;
    string str;
    cin >> str >> q;
    for (int i = 0; i < q; i++)
    {
        string op;
        int a, b;
        cin >> op >> a >> b;
        if (op == "print")
        {
            cout << str.substr(a, b-a+1) << endl;
        }
        else if (op == "reverse")
        {
            string sub = str.substr(a, b-a+1);
            for (int i = 0; i < b-a+1; i++)
            {
                str[a+i] = sub[sub.size()-i-1];
            }
        }
        else if (op == "replace")
        {
            string p;
            cin >> p;
            str = str.replace(a, b-a+1, p);
        }
    }
    return 0;
}


Measured memory_bytes: 3192
import Glibc
extension String: CollectionType {}

var inp = readLine()!.split(" ").map { Int($0)! }
if inp[0] + inp[1] < inp[2] + inp[3] {
  print("Right")
} else if inp[0] + inp[1] > inp[2] + inp[3] {
  print("Left")
} else {
  print("Balanced")
}

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

int main() {
  int N, D;
  cin >> N >> D;
  vector<vector<int>> coord(N, vector<int>(D));
  for (int i=0; i<N; ++i) {
    for (int j=0; j<D; ++j) {
      cin >> coord.at(i).at(j);
    }
  }
  int cnt = 0;
  for (int i=0; i<N-1; ++i) {
    for (int j=i+1; j<N; ++j) {
      int dist = 0;
      for (int k=0; k<D; ++k) {
        dist += pow(coord[i][k] - coord[j][k], 2);
      }
      int l = 1;
      while (true) {
        if (dist == pow(l, 2)) {
          ++cnt;
          break;
        } else if (dist < pow(l, 2)) {
          break;
        }
        ++l;
      }
    }
  }
  cout << cnt << endl;
}

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

using std::pair;
using std::vector;
using std::string;

typedef long long ll;
typedef pair<int, int> pii;
 
#define fst first
#define snd second
#define pb(a) push_back(a)
#define mp(a, b) std::make_pair(a, b)
#define debug(...) fprintf(stderr, __VA_ARGS__)
 
template <typename T> bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
 
const int oo = 0x3f3f3f3f;
 
template<typename T> T read(T& x) {
    int f = 1; x = 0;
    char ch = getchar();
    for(;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48; 
    return x *= f;
}

const int N = 200000;

int n, k;
int v[N + 5];

int main() {
#ifdef Wearry
    freopen("data.txt", "r", stdin);
    freopen("ans.txt", "w", stdout);
#endif
    read(n), read(k);

    int tot = 0;
    for(int i = 1; i <= n; ++i) {
        int x;
        read(x);
        ++ v[x];
    }
    std::sort(v + 1, v + n + 1); 

    int ans = 0;
    for(int i = 1; i <= n - k; ++i) {
        ans += v[i];
    }
    printf("%d\n", ans);
    
    return 0;
}


Measured memory_bytes: 1024
Q = split(readline())
N,L = parse(Int,Q[1]),parse(Int,Q[1])
word_list = []
for i in 1:N
    S = chomp(readline())
    push!(word_list,S)
end
sorted_word_list = sort(word_list)
ans = ""
for i in 1:length(sorted_word_list)
    ans = ans*string(sorted_word_list[i])
end
println(ans)

Measured memory_bytes: 112144
#include <iostream>
#include <algorithm>
#include <list>
#include <set>
#include <string>
#include <cstring>
using namespace std;
#define MOD 10000

pair<long long,bool> pastas[105];
long long ways[1005][3][2]={0};
int main(){
    long long n,k;
    
    cin>>n>>k;
    for(int i=0; i<=n; i++){
        pastas[i]=make_pair(0, false);
    }
    for(int i=1; i<=k; i++){
        int a,b;
        cin>>a>>b;
        pastas[a]=make_pair(b, true);
    }
    
    if(pastas[1].second){
        ways[1][pastas[1].first][0]=1;
    }else{
        ways[1][1][0]=1;
        ways[1][2][0]=1;
        ways[1][3][0]=1;
    }
    for(int i=2; i<=n; i++){
        if(pastas[i].second){
            if(pastas[i].first==1) ways[i][pastas[i].first][0]+=(ways[i-1][2][0]+ways[i-1][2][1]+ways[i-1][3][0]+ways[i-1][3][1]);
            if(pastas[i].first==2) ways[i][pastas[i].first][0]+=(ways[i-1][1][0]+ways[i-1][1][1]+ways[i-1][3][0]+ways[i-1][3][1]);
            if(pastas[i].first==3) ways[i][pastas[i].first][0]+=(ways[i-1][1][0]+ways[i-1][1][1]+ways[i-1][2][0]+ways[i-1][2][1]);
            ways[i][pastas[i].first][1]+=ways[i-1][pastas[i].first][0];
        }else{
            ways[i][1][0]+=(ways[i-1][2][0]+ways[i-1][2][1]+ways[i-1][3][0]+ways[i-1][3][1]);
            ways[i][2][0]+=(ways[i-1][1][0]+ways[i-1][1][1]+ways[i-1][3][0]+ways[i-1][3][1]);
            ways[i][3][0]+=(ways[i-1][1][0]+ways[i-1][1][1]+ways[i-1][2][0]+ways[i-1][2][1]);
            ways[i][1][1]+=ways[i-1][1][0];
            ways[i][2][1]+=ways[i-1][2][0];
            ways[i][3][1]+=ways[i-1][3][0];
        }
        ways[i][1][0]=ways[i][1][0]%MOD;
        ways[i][1][1]=ways[i][1][1]%MOD;
        ways[i][2][0]=ways[i][2][0]%MOD;
        ways[i][2][1]=ways[i][2][1]%MOD;
        ways[i][3][0]=ways[i][3][0]%MOD;
        ways[i][3][1]=ways[i][3][1]%MOD;
    }
    long long ans=0;
    /*for(int i=1; i<=3; i++){
        for(int j=0; j<=1; j++){
            ans+=ways[n][i][j]%MOD;
        }
    }*/
    ans+=ways[n][1][0];
    ans=ans%MOD;
    ans+=ways[n][1][1];
    ans=ans%MOD;
    ans+=ways[n][2][0];
    ans=ans%MOD;
    ans+=ways[n][2][1];
    ans=ans%MOD;
    ans+=ways[n][3][0];
    ans=ans%MOD;
    ans+=ways[n][3][1];
    ans=ans%MOD;
    
    cout<<ans%10000<<endl;
}

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

#ifdef DEBUG
#define PRINT(x)\
    cout<<"func "<<__func__<<": line "<<__LINE__<<": "<<#x<<" = "<<(x)<<endl;
#define PRINTA(a,first,last)\
    cout<<"func "<<__func__<<": line "<<__LINE__<<": "<<#a<<"["<<(first)<<", "<<(last)<<")"<<endl;\
    for (int i=(first);i<(last);++i){cout<<#a<<"["<<i<<"] = "<<(a)[i]<<endl;}
#else
#define PRINT(x)
#define PRINTA(a,first,last)
#endif

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

template <class T, class U> void amax(T& x, U y) {if (x < y) x = y;}
template <class T, class U> void amin(T& x, U y) {if (x > y) x = y;}

int main(void)
{

    int N;
    cin >> N;
    vector<int> C(N);
    vector<pii> P(N);
    REP(i, N) {
        cin >> C[i];
        P[i] = pii(C[i], i);
    }
    sort(all(P));
    vector<int> rank(N);
    REP(i, N) {
        rank[P[i].second] = i;
    }
    PRINTA(rank, 0, N);
    
    vector<ll> dp(N + 1);
    dp[N] = 1;

    RREP(i, N) {
        if (rank[i] + 1 < N && P[rank[i] + 1].first == C[i]) {
            int i_next = P[rank[i] + 1].second;
            //printf("C[%d] == C[%d] == %d\n", i, i_next, C[i]);
            if (i_next - i >= 2) {
                dp[i] = (dp[i + 1] + dp[i_next]) % MOD;
            } else {
                dp[i] = dp[i + 1];
            }
        } else {
            dp[i] = dp[i + 1];
        }
    }
    PRINTA(dp, 0, N);
    cout << dp[0] << endl;
    return 0;
}



Measured memory_bytes: 5504
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# greedy,2通りやる

N,*A = map(int,read().split())

def solve(A):
    # A[0] > 0 となるように
    cum = 0
    cnt = 0
    for x in A:
        if cum <= 0:
            # positiveにしたい
            cum += x
            if cum <= 0:
                cnt += (1 - cum)
                cum = 1
        else:
            # negativeにしたい
            cum += x
            if cum >= 0:
                cnt += (1 + cum)
                cum = -1
    return cnt

x = solve(A)
y = solve([-x for x in A])
answer = min(x,y)
print(answer)

Measured memory_bytes: 12460
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using static System.Console;
using Pair = System.Collections.Generic.KeyValuePair<int, int>;
//using System.Numerics;
//using static System.Math;

class Program
{
    static void Main()
    {
        //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        new Program().solve();
        Out.Flush();
    }
    Scanner cin = new Scanner();
    readonly int[] dd = { 0, 1, 0, -1, 0 };
    readonly int mod = 1000000007;
    readonly string alfa = "abcdefghijklmnopqrstuvwxyz";
    readonly string ALFA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    long N;
    void solve()
    {
        N = cin.nextlong;
        if (N % 2 == 0)
        {
            WriteLine(N + " " + N + " " + N / 2);
            return;
        }
        for (int i = 1; i <= 3500; i++)
        {
            for (int j = 1; j <= 3500; j++)
            {
                long bunbo = N * i * j;
                long bunsi = 4 * i * j - N * j - N * i;
                if (bunsi <= 0) continue;
                if (bunbo % bunsi == 0)
                {
                    WriteLine(i + " " + j + " " + bunbo / bunsi);
                    return;
                }
            }
        }
        
    }

}

class Scanner
{
    string[] s; int i;
    char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] scan { get { return ReadLine().Split(); } }
    public int[] scanint { get { return Array.ConvertAll(scan, int.Parse); } }
    public long[] scanlong { get { return Array.ConvertAll(scan, long.Parse); } }
    public double[] scandouble { get { return Array.ConvertAll(scan, double.Parse); } }
    public string next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = ReadLine();
            while (st == "") st = ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return next;
        }
    }
    public int nextint { get { return int.Parse(next); } }
    public long nextlong { get { return long.Parse(next); } }
    public double nextdouble { get { return double.Parse(next); } }
}

Measured memory_bytes: 13268
//#define NDEBUG

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define iceil(a, b) (((a) + (b) - 1) / (b))
#define tomax(a, b) ((a) = max((a), (b)))
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

//#define TEST

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

int main(){
    StarBurstStream

    int h, w, k;
    cin >> h >> w >> k;

    vector<ll> dp(w + 2);
    dp[1] = 1;

    for(int i = 1; i <= h; i++){

        vector<ll> dp2(w + 2);
        for(int j = 1; j <= w; j++){

            for(int t = 0; t < (1 << (w - 1)); t++){
//                cerr << "test " << t << "\n";
                t <<= 1;
                bool tmp = true;
                for(int l = 1; l < w; l++){
                    if((t & (1 << l)) && (t & (1 << (l + 1)))) tmp = false;
                }
//                cerr << "test " << t << " " << tmp << "\n";
                if(tmp){
//                cerr << t << "\n";
                    if(!(t & (1 << j)) && !(t & (1 << (j - 1)))) dp2[j] += dp[j];
                    if(t & (1 << (j - 1))) dp2[j] += dp[j - 1];
                    if(t & (1 << j)) dp2[j] += dp[j + 1];
                    dp2[j] %= MOD;
                }
                t >>= 1;
            }
        }
        dp = dp2;
//        printv(dp, cerr);
    }

    cout << dp[k] << "\n";

    return 0;
}

Measured memory_bytes: 256