akhauriyash/Code-Regression huggingface dataset:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    cnt = [0] * (N + 1)
    for n in (A + B):
        cnt[n] += 1
    if max(cnt) > N:
        print('No')
        return
    # Bを逆順にすると、真ん中あたりで重複のペアが生じうる。そこを解消する。
    B = B[::-1]
    dup, dup_indices = -1, list()
    for i in range(N):
        if A[i] == B[i]:
            dup = A[i]
            dup_indices.append(i)
    if dup == -1:
        # 同じ数字のペアがないので、そのまま出力
        print('Yes')
        print(' '.join(map(str, B)))
        return
    # 真ん中あたりの重複ペア部分を他と入れ替える
    indices = list()
    for i in range(N):
        if A[i] != dup and B[i] != dup:
            indices.append(i)
    indices = indices[:len(dup_indices)]
    for i, j in zip(dup_indices, indices):
        B[i], B[j] = B[j], B[i]
    print('Yes')
    print(' '.join(map(str, B)))


if __name__ == '__main__':
    main()

Measured memory_bytes: 48400
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define sz(x) ((int) (x).size())
#define all(x) ((x).begin(), (x).end())

signed main() {
#ifdef LOCAL
    assert(freopen("a.in", "r", stdin));
#endif
    ll q, h, s, d, n;
    cin >> q >> h >> s >> d >> n;
    s = min({s, h * 2, q * 4});
    d = min(d, s * 2);
    ll res = (n / 2) * d + (n % 2) * s;
    cout << res << '\n';
}


Measured memory_bytes: 256
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
      	int N = sc.nextInt();
      	int AC = 0;
      	int WA = 0;
      	int TLE = 0;
      	int RE = 0;
        String a;
        for (int i=0; i<N; i++) {
            a = sc.next();
          	if(a.equals("AC")){
              AC += 1;
            }
          	else if(a.equals("WA")){
              WA += 1;
            }
          	else if(a.equals("TLE")){
              TLE += 1;
            }
          	else if(a.equals("RE")){
              RE += 1;
            }
        }
      
       	System.out.println("AC x " + AC);
      	System.out.println("WA x " + WA);
      	System.out.println("TLE x " + TLE);
      	System.out.println("RE x " + RE);
    }
}

Measured memory_bytes: 58088
/*

  "With age, comes wisdom. With travel, comes understanding.
   Remember that happiness is a way of travel – not a destination"

*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define int            long long int
#define ld             long double
#define F              first
#define S              second
#define pb             push_back
#define si             set <int>
#define vi             vector <int>
#define pii            pair <int, int>
#define vpi            vector <pii>
#define vpp            vector <pair<int, pii>>
#define mii            map <int, int>
#define mpi            map <pii, int>
#define spi            set <pii>
#define endl           "\n"
#define sz(x)          ((int) x.size())
#define all(p)         p.begin(), p.end()
#define que_max        priority_queue <int>
#define que_min        priority_queue <int, vi, greater<int>>
#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)       for(auto x : a) cout << x << " "; cout << endl
#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)
{
     int x = 1;
     while (b)
     {
          if (b & 1) x *= a;
          a *= a;
          b >>= 1;
     }
     return x;
}

typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> Set;

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
     const char* comma = strchr (names + 1, ',');
     cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

const int N = 200005;
int a[N], n, m, k;
map <pii, int> mp;
vector <int> v[N], col;

void dfs(int i, int p, int c)
{
     int cc = c;
     for (auto x : v[i])
     {
          if (x != p)
          {
               int mn = min(x, i);
               int mx = max(x, i);
               mp[ {mn, mx}] = col[cc];
               cc++;
               cc %= k;
               dfs(x, i, cc);
          }
     }

}

void solve()
{
     int i, j;
     cin >> n;
     vpi e;
     for (i = 0; i < n - 1; i++)
     {
          int x, y; cin >> x >> y;
          if (x > y)
               swap(x, y);
          v[x].pb(y);
          v[y].pb(x);
          e.pb({x, y});
     }
     for (i = 1; i <= n; i++)
          k = max(k, sz(v[i]));

     for (i = 1; i <= k; i++)
          col.pb(i);

     dfs(1, 0, 0);
     cout << k << endl;
     for (auto x : e)
          cout << mp[x] << endl;

}

int32_t main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

     cout << setprecision(9) << fixed;
     clock_t z = clock();
     solve();
     cerr << "Run Time : " << ((double)(clock() - z) / CLOCKS_PER_SEC);

     return 0;
}

Measured memory_bytes: 18292
#include <bits/stdc++.h>
#define pt(sth) cout << sth << "\n"
#define chmax(a, b) {if(a<b) a=b;}
#define chmin(a, b) {if(a>b) a=b;}
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
static const ll INF=1e18;
static const ll MOD=1e9+7;
static const ll MAX=101010;

/*
 for(i=0; i<N; i++)
   cin >> a[i];
*/

ll dp[66], ep[3333];

int main(void) {
  ll i, j, k, l;
  
  
  ll A, B, C, D, E, F;
  cin >> A >> B >> C >> D >> E >> F;
  
  dp[0]=1;
  for(i=0; i<33; i++) {
    chmax(dp[i+A], dp[i]);
    chmax(dp[i+B], dp[i]);
  }
  
  ep[0]=1;
  for(i=0; i<3030; i++) {
    chmax(ep[i+C], ep[i]);
    chmax(ep[i+D], ep[i]);
  }
  
  
  P res=P(0, 0);
  for(i=1; i<33; i++) {
    for(j=0; j<3030; j++) {
      if(i*100+j>F) continue;
      if(i*E<j) continue;
      if(!dp[i]||!ep[j]) continue;
      
      if(res.second*(i*100+j)<=(res.first+res.second)*j) {
        res=P(i*100, j);
      }
        
    }
  }
  
  pt(res.first+res.second<<" "<<res.second);
  
}




Measured memory_bytes: 384
s = list(input())
k = int(input())
same = []
tmp = 1
ans = 0
tsunagi = 0
for i in range(len(s)-1):
         if s[i] == s[i+1]:
                  tmp += 1
         else:
                  same.append(tmp)
                  tmp = 1
same.append(tmp)
if s[0] == s[len(s)-1]:
         tsunagi = 1
if tmp == len(s):
         print((len(s)*k)//2)
elif tsunagi == 0:
         for i in range(len(same)):
                  ans += (same[i]//2)*k
         print(ans)
else:
         for i in range(1,len(same)-1):
                  ans += (same[i]//2)*k
         ans += ((same[0]+same[len(same)-1])//2)*(k-1)
         ans += (same[0]//2)+((same[len(same)-1])//2)
         print(ans)
         
         


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

int main() {

    int n;

    cin >> n;

    vector<int> v(n);

    vector<set<int>> numberMap(n);

    for(int i = 0; i < n; ++i) {
        char ch;
        cin >> ch;
        v[i] = ch - '0';
    }

    for(int i = 0; i < n; ++i) {

        if(i)
            numberMap[i] = numberMap[i - 1];
        numberMap[i].insert(v[i]);

    }

    int sum = 0;
    for(int i = 0; i <= 9; ++i) {
        for(int j = 0; j <= 9; ++j) {
            for(int k = 0; k <= 9; ++k) {

                int v_i = 0;
                for(v_i = 0; v_i < n - 2; ++v_i) 
                    if(v[v_i] == i)
                        break;

                if(v_i == n - 2)
                    continue;

                int v_j = v_i + 1;
                for( ; v_j < n - 1; ++v_j)
                    if(v[v_j] == j)
                        break;
                if(v_j == n - 1)
                    continue;
                
                int v_k = v_j + 1;
                for( ; v_k < n; ++v_k)
                    if(v[v_k] == k)
                        break;
                if(v_k == n)
                    continue;
                
                sum++;
            }
        }
    }

    cout << sum << endl;


    return 0;
}

Measured memory_bytes: 15872
from collections import defaultdict

N=int(input())

d = defaultdict(int)
for i in input().split():
    d[int(i)]+=1

ans=0
for j in d.keys():
    if d[j]>j:
        ans+=d[j]-j
    elif d[j]<j:
        ans+=d[j]

print(ans)



Measured memory_bytes: 23660
N,M = map(int,input().split())
INF = float('inf')
V = [INF] * (1<<N)
V[0] = 0
for i in range(M):
    v,_ = map(int,input().split())
    b = 0
    s = list(map(int,input().split()))
    for a in s:
        b |= (1<<(a-1))
    V[b] = min(V[b], v)

vbs = []
for b,v in enumerate(V):
    if v==INF: continue
    vbs.append((v,b))

for v,b in vbs:
    for c in range(1<<N):
        if V[c] == INF: continue
        V[b|c] = min(V[b|c], V[b]+V[c])

print(V[-1] if V[-1] < INF else -1)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define INF 0x3f3f3f3f
using namespace std;
int a,b;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>a>>b;
	if (a==1) a=14;
	if (b==1) b=14;
	if (a>b) cout<<"Alice";
	else if (a<b) cout<<"Bob";
	else cout<<"Draw";
	return 0;
}

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

using namespace std;

long long L[87];

int main() {
    int N;
    cin >> N;
    L[0] = 2;
    L[1] = 1;
    for (int i = 2; i < 87; ++i) {
        L[i] = L[i - 1] + L[i - 2];
    }
    cout << L[N] << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
  int a,b,c,d,e,f,i;
  e=0;
  f=0;
  cin>>a>>b>>c;
  for(i=0;i<b;++i){
    cin>>d;
    if(d>c)++e;
    else ++f;}
  cout<<(e<f?e:f)<<endl;}


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

using namespace std;

int main()
{
    string input;
    string first, second;
    int max_freq = 0;
    map<string, int> data;

    cin >> input;
    first = second = input;

    while (cin >> input) {
        if (input.size() > second.size())
            second = input;

        data[input]++;

        if (data[input] > max_freq) {
            first = input;
            max_freq = data[input];
        }
    }

    cout << first << " " << second << endl;

    return 0;
}

Measured memory_bytes: 1196
#include <cstdio>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

int main() {

	int INF = 10000000;

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

	vector<pair<int, int>> G[n];
	for (int i = 0; i < n; ++i) {
		int from;
		scanf("%d", &from);

		int v;
		scanf("%d", &v);

		for (int j = 0; j < v; ++j) {
			int to;
			int w;
			scanf("%d %d", &to, &w);
			G[from].push_back(make_pair(to, w));
		}
	}

	int C[n];
	for (int i = 0; i < n; ++i)
		C[i] = INF;

	int color[n];
	int WHITE = 0;
	int BLACK = 1;
	for (int i = 0; i < n; ++i)
		color[i] = WHITE;

	priority_queue<pair<int, int>> PQ;
	PQ.push(make_pair(0, 0));
	C[0] = 0;
	while (!PQ.empty()) {
		int u = PQ.top().second;
		PQ.pop();
		color[u] = BLACK;
		for (int i = 0; i < (int) G[u].size(); ++i) {
			auto c = G[u][i];
			if (color[c.first] != BLACK && c.second + C[u] < C[c.first]) {
				C[c.first] = c.second + C[u];
				PQ.push(make_pair(C[c.first] * -1, c.first));
			}
		}
	}

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

	return 0;
}

Measured memory_bytes: 7836
/********************************************//**
 ****** Author: Shivam Kejriwal *****************
 ****** Handle: techno_phyle    *****************
 ***********************************************/

#include<bits/stdc++.h>
using namespace std;

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
typedef long long ll;

#define mod 1000000007
#define N 100010
#define M 200010
#define db(a) cout << a << endl
#define db2(a,b) cout << a << " " << b << endl
#define dbp(a) cout << a.first << " " << a.second << endl
#define adb(a) for(auto it:a) cout << it << " "; cout << endl
#define adbp(a) for(auto it:a) cout << it.first << " " << it.second << endl
#define pb push_back
#define mp make_pair
typedef pair<double, long> key;

struct comp {
    bool operator()(pair<int,int> p1, pair<int,int> p2) {
        if (p1.first < p2.first) return false;
        if (p2.first < p1.first) return true;
        return p1.second < p2.second;
    };
};
//greater<pair<int,int> , greater<int>>

int dp[N][3];
int main(){
	fastIO;
    //#ifndef ONLINE_JUDGE
    //    freopen("../input.txt", "r", stdin);
    //   freopen("../output.txt","w",stdout);
    //#endif
	int n;
    cin >> n;
    for(int i=1;i<=n;i++){
    	int a,b,c;
    	cin >> a >> b >> c;
    	if(i==1){
    		dp[i][0] = a;
    		dp[i][1] = b;
    		dp[i][2] = c;
    	}
    	else{
    		dp[i][0] = a + max(dp[i-1][1],dp[i-1][2]);
    		dp[i][1] = b + max(dp[i-1][0],dp[i-1][2]);
    		dp[i][2] = c + max(dp[i-1][1],dp[i-1][0]);
    	}
    }
    cout << max(dp[n][0] , max(dp[n][1],dp[n][2])) << endl;
	return 0;

}



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

inline int getint()
{
	static char c;
	while ((c = getchar()) < '0' || c > '9');

	int res = c - '0';
	while ((c = getchar()) >= '0' && c <= '9')
		res = res * 10 + c - '0';
	return res;
}

const int MaxM = 100000;
const int MaxN = 100000;

int x, m, n;
int rev[MaxM + 1];

int l, r, c;

inline void update(int delta)
{
	c += delta;

	if (l > x - c)
		l = r = x - c;
	else
		r = min(x - c, r);

	if (r < -c)
		l = r = -c;
	else
		l = max(l, -c);
}

int main()
{
	cin >> x >> m, r = x;
	for (int i = 1; i <= m; ++i)
		rev[i] = getint();

	cin >> n;

	int d = 0, k = 1, coef = -1;
	for (int i = 1; i <= n; ++i)
	{
		int t = getint(), a = getint();

		while (k <= m && rev[k] <= t)
		{
			update(coef * (rev[k] - d));
			d = rev[k++];
			coef = -coef;
		}
		update(coef * (t - d)), d = t;

		if (a <= l)
			printf("%d\n", l + c);
		else if (a <= r)
			printf("%d\n", a + c);
		else
			printf("%d\n", r + c);
	}

	return 0;
}

Measured memory_bytes: 1536
import java.util.*;

public class Main {
  private static final int MOD = 1_000_000_007;
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int K = sc.nextInt();
    int[] A = new int[N];
    for (int i = 0; i < N; i++) {
      A[i] = sc.nextInt();
    }
    // inside A
    int a = 0;
    for (int i = 0; i < N-1; i++) {
      for (int j = i+1; j < N; j++) {
        if (A[i] > A[j]) {
          a++;
        }
      }
    }
    
    Arrays.sort(A);
    int sumP = 0;
    for (int i = N-1; i >= 1; i--) {
      for (int j = i-1; j >= 0; j--) {
        if (A[i] > A[j]) {
          sumP++;
        }
      }
    }
    // p0*(K-1) + p0*(K-2) + .... + p0
    // p1*(K-1) + p1*(K-2) + .... + p1
    //
    // K(K-1)/2 * (p0+p1+....)
    
    long KK = K%2 == 0 ? (long)K/2*(K-1) : (long)K*((K-1)/2);
    long ans = (((long)a*K)%MOD + ((KK%MOD)*sumP)%MOD)%MOD;
    
    System.out.println(ans);
  }
}

Measured memory_bytes: 26512
#include<bits/stdc++.h>
#include<string.h>
 
typedef long long int ll;
#define all(x) (x).begin(), (x).end()
 
using namespace std;

int nxt() {
    int x;
    cin >> x;
    return x;
}

ll nxtl(){
    ll x;
    cin>>x;
    return x;
}
 
void SieveOfEratosthenes(int n,vector <int> &primes) 
{ 
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          primes.push_back(p);
} 
 
ll max(ll a,ll b)
{
    if(a>b)
        return a;
    return b;
}
 
ll power(ll x, ll y,ll mod) 
{ 
    ll temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2,mod); 
    if (y%2 == 0) 
        return (temp*temp)%mod; 
    else
        return (((x*temp)%mod)*temp)%mod; 
} 

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll mod=998244353;
    ll n=nxtl(),s=nxtl();
    vector <ll> v(n);
    generate(all(v),nxtl);
    vector <vector <ll> > dp;
    vector <ll> row;
    row.resize(s+1,0);
    dp.resize(n,row);
    if(v[0]<=s)
        dp[0][v[0]]+=1;
    vector <ll> prefix(s+1);
    prefix=dp[0];
    for(int i=1;i<n;i++)
    {
        if(v[i]<=s)
            (dp[i][v[i]]+=(i+1))%=mod;
        for(int j=s;j-v[i]>=0;j--)
            (dp[i][j]+=prefix[j-v[i]])%=mod;
        for(int j=0;j<=s;j++)
            prefix[j]=(prefix[j]+dp[i][j])%mod;
    }
    ll test=0;

    for(int i=0;i<n;i++)
        {
            test=(test+dp[i][s]*(n-i))%mod;
        }
    cout<<test<<endl;

    return 0;   
}


 
 


Measured memory_bytes: 70784
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; 
#define arrlen(arr) (sizeof(arr)/sizeof(arr[0]))
#define Sort(arr) sort(arr, arr+arrlen(arr))
#define For(i,s,n) for(int i=s;i<n;i++)
	
//最大公約数
ll GCD(ll a,ll b){
	if(a==0) return b;
	if(b==0) return a;
	if(a>=b) return GCD(a%b,b);
	else return GCD(a,b%a);
}
	
ll f(ll N,ll C,ll D){
	ll lcm=C*D/GCD(C,D);
	//cout << N-N/C-N/D-N/lcm;
	return (N-N/C-N/D+N/lcm);
}
	
int main(){
	ll A,B,C,D;
	cin >> A >> B >> C >> D;
	cout << f(B,C,D)-f(A-1,C,D);
}
	

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <algorithm>
#include <utility>
#include <vector>
#include <map>
using namespace std;
#define mp  std::make_pair
#define ll long long int
#define abs(n) ((n>0)?(n):((n)*(-1)))
#define CEIL(a,b) (((a) + ((b)-1)) / (b))
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define VREP(v) for(std::vector<ll>::iterator itr = (v).begin(); itr != (v).end();itr++)
#define VALL(v) ((v).begin(),(v).end())
#define errln(v) cerr << (v) << endl;
#define println(v) cout << (v) << endl;



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

	ll X[n],sorted[n];
	REP(i,n) {
		cin >> X[i];
		sorted[i] = X[i];
	}

	sort(sorted,sorted+n);

	ll c1 = sorted[n/2-1];
	ll c2 = sorted[n/2];

	REP(i,n){
		if(X[i]<= c1){
			println(c2);
		}else{
			println(c1);
		}
	}


	return 0;

}


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

int main(){
    int n;
    cin >> n;
    vector <string> s(n);
    rep(i,n){
        cin >> s[i];
    }
     int a=0,b=0,l,ab=0,k=0;
     string ss;

     rep(i,n){
         ss=s[i];
         l=ss.size();
         if(ss[0]=='B' and ss[l-1]=='A'){
             ++ab;
         }
         else if(ss[0]=='B'){
             ++b;
         }
         else if(ss[l-1]=='A'){
             ++a;
         }

         rep(j,l-1){
             if(ss.substr(j,2)=="AB"){
                 ++k;
             }
         }

         
     
     }
    //cout << ab << a << b << k << endl;
     int ans;
     ans=k;
     int m,m2;
     m=max(a,b)-min(a,b);
     if(ab<=m){
         ans+=min(a,b)+ab;
     }
     else{
         ans+=max(a,b)+(ab-m);
         if(a==0 and b==0){
             --ans;
         }
     }

     

     cout << ans << endl;


    

    return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> to;
vector<int> dist, used;
typedef pair<int, int> P;
int N;
vector<int> flag;
int dfs(int s){
    if(used[s] == 1) {
        if(flag[s] == 0) return -1; 
        return dist[s];
    }
    used[s] = 1;
    dist[s] = 0;
    for(int i: to[s]){
        int res = dfs(i);
        if(res == -1) return -1;
        dist[s] = max(dist[s], res + 1);
    }
    flag[s] = 1;
    return dist[s];
} 
int main(){
    cin >> N;
    vector<vector<int>> a(N, vector<int> (N - 1));
    to.resize(N * (N - 1) / 2);
    for(int i =0 ; i< N; i++){
        for(int j = 0;j < N - 1; j++) {
            cin >> a[i][j];
            a[i][j]--;
        }
    }
    int ind[N][N];
    int cnt = 0;
    for(int i = 0; i < N; i++){
        for(int j = i + 1; j < N; j++){
            ind[i][j] = cnt;
            cnt++;
        }
    }
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N - 2; j++){
            int s1 = i, t1 = a[i][j], t2 = a[i][j + 1];
            int s2 = s1;
            if(s1 > t1) swap(s1, t1);
            if(s2 > t2) swap(s2, t2);
            int ind1 = ind[s1][t1], ind2 = ind[s2][t2];
            to[ind2].push_back(ind1);
        }
    }
    dist.resize(N * (N - 1) / 2, 0);
    used.resize(N * (N - 1) / 2, 0);
    flag.resize(N * (N - 1) / 2, 0);
    int ans = 0;
    for(int i = 0; i < N * (N - 1) / 2; i++){
        int res = dfs(i);
        if(res == -1){
            cout << -1 << endl;
            return 0;
        }
        ans = max(ans, dfs(i));
    }
    cout << ans + 1 << endl;
}

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

long long gcd(long long a, long long b){
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}

long long lcm(long long a, long long b)
{
   return a * b / gcd(a, b);
}

int main(){
  long long A,B,C,D;  cin >> A >> B >> C >> D;
  long long countC = 0;
  long long countD = 0;
  long long countCD = 0;
  long long g = lcm(C,D);
  if(A%C == 0){
    countC = (B-B%C-A)/C + 1;
  }else{
    countC = (B-B%C-A-C+A%C)/C + 1;
  }
  if(A%D == 0){
    countD = (B-B%D-A)/D + 1;
  }else{
    countD = (B-B%D-A-D+A%D)/D + 1;
  }
  if(A%g == 0){
    countCD = (B-B%g-A)/g + 1;
  }else{
    countCD = (B-B%g-A-g+A%g)/g + 1;
  }
  long long ans = 0;
  ans = B - A + 1 - (countC + countD - countCD);
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define pii pair<int,int> 
#define pb push_back
#define INF INT_MAX 
#define mod 1000000007ll
#define fi first
#define se second
#define f(i,p,q) for(int i=p;i<q;i++)
#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define psi(a) printf(" %d",a)
#define poi(a) printf("%d",a)
#define sl(a) scanf("%lld",&a)
#define pl(a) printf("%lld\n",a)
#define Nline() printf("\n")
#define sstr(str) scanf("%s",str)
#define pstr(str) printf("%s\n",str)
#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define vi vector<int>
#define vvi vector<vi>
#define all(v) (v).begin(),(v).end()
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())
#define ios ios::sync_with_stdio(false); cin.tie(0);cout.tie(NULL);
int main() {
    ios;
   ll n,x,y;
   cin>>n>>x>>y;
   vector<vector<int>>v(2005);
   f(i,1,n){
       v[i].pb(i+1);
       v[i+1].pb(i);
   }
   v[x].pb(y);
   v[y].pb(x);
   ll ans[n+1];
   f(i,0,n+1)ans[i]=0;
  /* f(i,1,n+1){
    for(int j=0;j<v[i].size();j++)
    { cout<<v[i][j]<<" ";
    } cout<<"\n";
   }*/
   bool vis[n+1];
   f(i,1,n+1)vis[i]=0;
   for(int i=1;i<=n;i++)
   {
       vis[i]=1;
       queue<pair<int,int>>q;
       q.push({i,1});
       while(!q.empty()){
           int x=q.front().fi;
           int d=q.front().se;
           q.pop();
           for(int j=0;j<v[x].size();j++){
               if(!vis[v[x][j]]){
                   vis[v[x][j]]=1;
                   ans[d]++;
                   q.push({v[x][j],d+1});
               }
           }
       }
      // for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
        // cout<<"\n";
       f(i,1,n+1)vis[i]=0;
   }
   for(int i=1;i<n;i++)
   cout<<ans[i]/2<<" ";
 
    
}

Measured memory_bytes: 384
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
typedef long long ll;

int main()
{
    int ans;
    char s;

    scanf("%c",&s);
    if(s=='R')
    {
        scanf("%c",&s);
        if(s=='R')
        {
            scanf("%c",&s);
            if(s=='R')
            {
                ans=3;
            }
            else
            {
                ans=2;
            }
        }
        else
        {
            ans=1;
        }
        
    }
    else
    {
        scanf("%c",&s);
        if(s=='R')
        {
            scanf("%c",&s);
            if(s=='R')
            {
                ans=2;
            }
            else
            {
                ans=1;
            }
        }
        else
        {
            scanf("%c",&s);
            if(s=='R')
            {
                ans=1;
            }
            else
            {
                ans=0;
            }
            
        }
        
    }

    printf("%d\n",ans);

    return 0;
}

Measured memory_bytes: 1672
a = input()
b = 0
c = 0
for i in range(len(a)):
  if a[i] == 'A' or a[i] == 'C' or a[i] == 'G' or a[i] == 'T':
    b += 1
    c = max(c,b)
  else:
    b = 0
print(c)

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

int main(void){
  while(1){
    int N;
    cin >> N;
    if(N == 0){return 0;}

    int W,H;
    cin >> W;
    cin >> H;
    bool f[W][H];

    int x[N];
    int y[N];

    for(int i = 0 ; i < W ; i++){
      for(int j = 0 ; j < H ; j++){
        f[i][j] = false;
      }
    }

    for(int i = 0 ; i < N ; i++){
      cin >> x[i]; x[i]--;
      cin >> y[i]; y[i]--;
      f[x[i]][y[i]] = true;
    }


    int S,T;
    cin >> S;
    cin >> T;

    int max = -1;

    for(int i = 0 ; i <= W - S ; i++){
      for(int j = 0 ; j <= H - T ; j++){
        int cnt = 0;
        for(int I = 0 ; I < S ; I++){
          for(int J = 0 ; J < T ; J++){
            if(f[i+I][j+J] == true){cnt++;}
          }
        }
        if(cnt > max){max = cnt;}
      }
    }

    cout << max << endl;;
  }
}

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

import sys


def string_to_list_spliter():
    lst = [int(i) for i in sys.stdin.readline().split()]
    return lst


def main():
    # XXX: N????????´??°??????????????????????????????AOJ?????£???????????????
    n = sys.stdin.readline()
    lst = string_to_list_spliter()
    print(min(lst), max(lst), sum(lst))


if __name__ == '__main__':
    main()

Measured memory_bytes: 8704
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <map>
#include <set>
#include <sstream>
#include <stdio.h>
#include <cstdio>
#include <cstring>

using namespace std;

#define Rep(i,a,b) for(int i = a; i < b; i++)
#define rep(i,b) Rep(i,0,b)
#define rrep(i,a) for(int i = a; i >= 0; i--)
#define allof(a) (a).begin(), (a).end()

typedef long long ll;
const int inf = 1e9 + 7;
const ll infll = 1ll << 60ll;
const ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

/*
// 最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

// 最小公倍数
ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}*/


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

	ll n;
	cin >> n;
	vector<ll> a(n);
	ll num = 0;
	rep(i, n) {
		cin >> a[i];
		num = max(num, a[i]);
	}


	// 中間くらいの値が大きい

	sort(allof(a));

	double tnum = (double)num / (double)2;
	ll tn = lower_bound(allof(a), tnum) - a.begin();
	if (tnum - a[tn - 1] <= a[tn] - tnum) {
		cout << num << " " << a[tn - 1] << endl;
	}
	else
		cout << num << " " << a[tn] << endl;
	return 0;
}

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

#define ll long long
#define llu unsigned long long
#define ld long double
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define pf push_front
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define ff first
#define ss second
#define endl '\n'
#define vvi(v, n, m) vector<vi> v(n, vi(m))
#define vvll(v, n, m) vector<vll> v(n, vll(m))
#define all(x) (x).begin(), (x).end()
#define present(v,x) (v).find(x) != (v).end()
#define cpresent(v,x) (find(all(v),x) != (v).end())
#define mset(x,v) memset(x, v, sizeof(x))
#define sz(x) (int)x.size()

string to_string(string s) { return '"' + s + '"';}
string to_string(char s) { return string(1, s);}
string to_string(const char* s) { return to_string((string) s);}
string to_string(bool b) { return (b ? "true" : "false");}
void debug_out() { cout << ""; }
template <typename A> string to_string(A);
template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}
template <typename A> string to_string(A v) {bool f = 1; string r = "{"; for (const auto &x : v) {if (!f)r += ", "; f = 0; r += to_string(x);} return r + "}";}
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {cout << " " << to_string(H); debug_out(T...);}
#define pr(v, n) {for(int j=0; j<n; j++){debug_out(v[j]); if(j<n-1) cout<<",";}}
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__); { cout << endl; }
#define dbg1d(v, n) cout << "[" << #v << "]: {"; pr(v, n); {cout << " }" << endl;}
#define dbg2d(v, n, m) cout<<"["<<#v<<"]:"<<endl;{for(int i=0; i<n; i++){cout<<right<<setw(10)<<"["+to_string(i)+"] {";pr(v[i],m);{cout<<" }"<<endl;}}}
#define shout()  {cout << "I'm Here...!!!" << endl;}

inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int addmod(int a, int val, int p = MOD) {{if ((a = (a + val)) >= p) a -= p;} return a;}
inline int submod(int a, int val, int p = MOD) {{if ((a = (a - val)) < 0) a += p;}return a;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	string s;
	cin >> s;
	int d;
	cin >> d;

	vector<int> k((int)s.length()+1);
	int n = k.size()-1;
	for(int i=1; i<=n; i++)
		k[i] = s[i-1]-'0';

	int dp[n+1][d][2];
	mset(dp, 0);
	dp[0][0][true] = 1;

	for(int i=1; i<=n; i++)
		for(int j=0; j<d; j++){
			dp[i][j][false] = 0, dp[i][j][true] = 0;
			for(int dig=0; dig<=9; dig++){
				int last_sum = ((j-dig)%d+d)%d;
				dp[i][j][false] = addmod(dp[i][j][false], dp[i-1][last_sum][false]);
				if(dig<k[i])
					dp[i][j][false] = addmod(dp[i][j][false], dp[i-1][last_sum][true]);
			}
			int last_sum = ((j-k[i])%d+d)%d;
			dp[i][j][true] = addmod(dp[i][j][true], dp[i-1][last_sum][true]);
		}

	int res = submod(addmod(dp[n][0][true], dp[n][0][false]), 1);
	cout << res << endl;

	return 0;
}

Measured memory_bytes: 8192
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>
#include<deque>
#include<queue>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000000 + 7;

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	Int K;
	cin >> K;

	for (Int N = 2; N < 51; N++) {
		if (K % N == 0) {
			if (N-1+K/N<=1e16+1000) {
				cout << N << "\n";
				for (int i = 0; i < N; i++) {
					cout << N-1+K/N << " ";
				}
				return 0;
			}
		}
		else {
			if (N + K / N <= 1e16 + 1000) {
				Int a = 2 * N + K / N - K % N;
				Int b = (N * (N - 1) + K - a * (K % N)) / (N - K % N);
				cout << N << "\n";
				for (int i = 0; i < K%N; i++) {
					cout << a << " ";
				}
				for (int i = 0; i < N-K%N; i++) {
					cout << b << " ";
				}
				return 0;
			}
		}
	}
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] N = sc.next().toCharArray();
		long ans = 0;
		
		for(int i=1; i<=9; i++) {
			for(int j=1; j<=9; j++) {
				ans += count(i, j, N)*count(j, i, N);
			}
		}
		
		System.out.println(ans);
		sc.close();
	}
	
	static long count(int a, int b, char[] N) {
		long ans = 0;
		if((a==b)&&(N.length>1 || N[N.length-1]-'0'>=a))
			ans++;
		for(int i=0; i<=N.length-2; i++) {
			if(N.length > i+2) {
				int temp = 1;
				for(int j=0; j<i; j++)
					temp *= 10;
				ans += temp;
			} else if(N.length == i+2) {
				if(N[0]-'0' > a) {
					int temp = 1;
					for(int j=0; j<i; j++)
						temp *= 10;
					ans += temp;
				} else if(N[0]-'0'== a) {
					String num = String.valueOf(N);
					num = num.substring(1, num.length()-1);
					if(num.length()==0)
						num = "0";
					int add = Integer.valueOf(num);
					if(N[N.length-1]-'0'>=b)
						add++;
					ans += add;
				}
			}
		}
		return ans;
	}
}

Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF=1001001001;
const long long mod=998244353;

int main(){
  int64_t N,K,S;
  cin>>N>>K>>S;
  vector<int>ans(N);
  int cnt=K;
  for(int i=0;i<N;i++){
    if(cnt>0){cnt--;ans[i]=S;}
    else{
      if(S==1000000000){ans[i]=1;}
      else{ans[i]=1000000000;}
    }
  }
  for(int i=0;i<N;i++){
    cout<<ans[i]<<" ";
  }cout<<endl;
  return 0;                       
}

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

using namespace std;
using ll = long long;

#define REP(i, n) for (ll i = 0; i < n; i++)
#define INF 9223372036854775807
#define all(x) (x).begin(), (x).end()

ll ts = 1000000007;

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

  ll n;
  cin >> n;

  cout << n / 3 << "\n";
}

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

using ll=int64_t;
#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(),x.end()
#define REACH cerr<<"reached line "<<__LINE__<<endl
#define DMP(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define ZERO(x) memset(x,0,sizeof(x))

using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"[";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"]";
	return os;
}

int read(){
	int i;
	scanf("%" SCNd64,&i);
	return i;
}

void printSpace(){
	printf(" ");
}

void printEoln(){
	printf("\n");
}

void print(int x,int suc=1){
	printf("%" PRId64,x);
	if(suc==1)
		printEoln();
	if(suc==2)
		printSpace();
}

string readString(){
	static char buf[3341000];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341000];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(a>b)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

const int inf=LLONG_MAX/3;

const int Nmax=100010;
vector<pi> g[Nmax];
bool vis[Nmax];
int val[Nmax];

void Yes(){
	cout<<"Yes"<<endl;
	exit(0);
}

void No(){
	cout<<"No"<<endl;
	exit(0);
}

void dfs(int v,int d,int&mn,int&mx){
	if(vis[v]){
		if(val[v]!=d)No();
		return;
	}
	vis[v]=true;
	val[v]=d;
	chmin(mn,d);
	chmax(mx,d);
	for(auto e:g[v])dfs(e.first,d+e.second,mn,mx);
}

signed main(){
	int n=read(),m=read();
	REP(i,m){
		int u=read()-1,v=read()-1,d=read();
		g[u].PB(pi(v,d));
		g[v].PB(pi(u,-d));
	}
	REP(i,n)if(!vis[i]){
		int mn=inf,mx=-inf;
		dfs(i,0,mn,mx);
		if(mx-mn>1000000000)No();
	}
	Yes();
}

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

#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define RFOR(i, a, b) for(int i=(a); i>=(b); i--)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) RFOR(i, n, 0)
#define dump(x)  cout << #x << " = " << (x) << endl;

typedef long long ll;
typedef pair<int, int> ii;
const int mod = 1e9+7;
const ll INF = 1e18;
const int inf = 1e9;

void solve()
{
  int x; cin>>x;
  if (x<1200) cout << "ABC" << endl;
  else cout << "ARC" << endl;
}

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


Measured memory_bytes: 256
import sys
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] == "#" and (i == 0 or s[i-1][j] == ".") and (i == h-1 or s[i+1][j] == ".") and (j == 0 or s[i][j-1] == ".") and (j == w-1 or s[i][j+1] == "."):
            print("No")
            sys.exit()
print("Yes")

Measured memory_bytes: 3064
#include <bits/stdc++.h> 
using namespace std;
using ll = long long;
template<typename T> using v2 = vector<vector<T>>;
template<typename T> inline v2<T> fill(int r, int c, const T& t){ return v2<T>(r, vector<T>(c, t)); }
#define F first
#define S second

const int MOD = 1e9+7; //998244353;

v2<vector<int>> dp;

int f(int index, int n0, int n9){
    if(n0<0 || n9<0) return 0;
    if(index==-1) return n0==0 && n9==0;
    if(dp[index][n0][n9]!=-1) return dp[index][n0][n9];

    if(n0==0&&n9==0){
        dp[index][0][0] = (8LL*f(index-1,0,0))%MOD;
    }
    else if(n0==0&&n9==1){
        dp[index][0][1] = (9LL*f(index-1,0,1) + f(index-1,0,0))%MOD;
    }
    else if(n0==1&&n9==0){
        dp[index][1][0] = (9LL*f(index-1,1,0) + f(index-1,0,0))%MOD;
    }
    else{
        dp[index][1][1] = (10LL*f(index-1,1,1) + f(index-1,0,1) + f(index-1,1,0))%MOD;
    }

    return dp[index][n0][n9];
}

void solve(){
    int n;
    cin>>n;

    dp = fill(n, 2, vector<int>(2, -1));

    int ans = f(n-1,1,1);
    cout << ans << "\n";
}

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

Measured memory_bytes: 198444
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

const int MOD = 1e9 + 7;
const int iINF = 1000000000;
const long long int llINF = 1000000000000000000;

using namespace std;
using ll = long long int;
using vv = vector<vector<ll>>;
using edge = struct {
  int to;
  int cost;
};
#define REP(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define AUTO(i, m) for (auto &i : m)
#define ALL(a) (a).begin(), (a).end()
#define MAX(vec) *std::max_element(vec.begin(), vec.end());
#define MIN(vec) *std::min_element(vec.begin(), vec.end());
#define BIT(n, num) std::bitset<(n)>((num)).to_string()
#define REV(T) greater<T>()
#define PQ priority_queue<ll, vector<ll>, greater<ll>>

typedef pair<ll, ll> Pair;
bool pairCompare(const Pair &firstElof, const Pair &secondElof) {
  return firstElof.second > secondElof.second;
}

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main() {
  ll A, B;
  cin >> A >> B;
  ll ans = 0;
  B++;
  REP(i, 41) {
    ll a = A % (ll)pow((ll)2, i + 1);
    ll b = B % (ll)pow((ll)2, i + 1);
    ll c = (A / (ll)pow((ll)2, i + 1)) * (ll)pow((ll)2, i);
    ll d = (B / (ll)pow((ll)2, i + 1)) * (ll)pow((ll)2, i);
    if (a > (ll)pow((ll)2, i))
      c += a - (ll)pow((ll)2, i);
    if (b > (ll)pow((ll)2, i))
      d += b - (ll)pow((ll)2, i);
    if ((d + c) % 2 != 0)
      ans += (ll)pow((ll)2, i);
  }
  cout << ans << endl;

  return 0;
}


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

string s;
int n, k;
ll dp[101][5][2];
int main() {
    cin >> s >> k;
    n = s.size();
    dp[0][0][0] = 1; 

    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= k; j++) {
            // op = 0 = 
            if(s[i] == '0') dp[i+1][j][0] += dp[i][j][0];
            else {
                dp[i+1][j][1] += dp[i][j][0];
                dp[i+1][j+1][0] += dp[i][j][0];
                dp[i+1][j+1][1] += dp[i][j][0]*(s[i]-'1');
            }

            // op = 1 <
            dp[i+1][j][1] += dp[i][j][1];
            dp[i+1][j+1][1] += dp[i][j][1] * 9;
        }
    }

    cout << dp[n][k][0] + dp[n][k][1] << endl;
}


Measured memory_bytes: 256
from collections import deque

s=input()

d=deque()
for i in s: #10**5
  d.append(i)
  
v=1

q=int(input())

for i in range(q): #2*10**5
  a=input()
  if len(a)==1:
    if v:
      v=0
    else:
      v=1
  else:
    b,f,c=a.split()
    if f=="1":
      if v:
        d.appendleft(c)
      else:
        d.append(c)
    else:
      if v:
        d.append(c)
      else:
        d.appendleft(c)
        
if v:
  for i in range(len(d)):
    print(d[i],end="")
else:
  for i in range(len(d)):
    print(d[len(d)-1-i],end="")
    
print()

Measured memory_bytes: 93784
#! coding:UTF-8
data = list(map(int,input().split(" ")))
if 1 in data:
	if data.count(1) == 2:
		print("Draw")
	elif data.index(1) == 0:
		print("Alice")
	else:
		print("Bob")
else:
	if data[0] == data[1]:
		print("Draw")
	elif data[0] > data[1]:
		print("Alice")
	else:
		print("Bob")


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
const ll INF = 1e12;
const int MOD = 1000000007;


int main() {
        int h,w;
        cin >> h >> w;
        vector<string> maze(h);
        rep(i,h) cin >> maze.at(i);
        vector<vector<vector<ll>>> dp(h,vector<vector<ll>>(w,vector<ll>(2,INF)));
        if(maze.at(0).at(0) == '.'){
                dp[0][0][0] = 0;
        }else{
                dp[0][0][1] = 1;
        }
        
        rep(i,h)rep(j,w){
                if(maze.at(i).at(j) == '.'){
                        if(i > 0) dp.at(i).at(j).at(0) = min(dp.at(i-1).at(j).at(0),dp.at(i-1).at(j).at(1));
                        if(j > 0) dp.at(i).at(j).at(0) = min(dp.at(i).at(j).at(0),min(dp.at(i).at(j-1).at(0),dp.at(i).at(j-1).at(1)));
                }
                else{
                     if(i > 0) dp.at(i).at(j).at(1) = min(dp.at(i-1).at(j).at(0) + 1,dp.at(i-1).at(j).at(1));
                     if(j > 0) dp.at(i).at(j).at(1) = min(dp.at(i).at(j).at(1) ,min(dp.at(i).at(j-1).at(0) + 1,dp.at(i).at(j-1).at(1)));   
                }
        }   
        cout << min(dp[h-1][w-1][0],dp[h-1][w-1][1]) << endl;   
        return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
using namespace std;
int main(){
	int n;
	int p[50];
	int q[50];
	cin >> n;
	for(int i = 0;i < n;i++){
		cin >> p[i];
		q[i] = p[i];
	}
	sort(p, p + n);
	int count = 0;
	for(int i = 0;i < n;i++){
		if(p[i] != q[i]) count++;
	}
	if(count <= 2){
		cout << "YES" << endl;
	}else{
		cout << "NO" << endl;
	}
}

Measured memory_bytes: 256
#include <iostream>

int main() {
  int n;
  int G[110][110];
  std::cin >> n;

  for(int i=0; i<n; ++i) {
    for(int j=0; j<n; ++j) G[i][j] = 0;
  }

  for(int i=0; i<n; ++i) {
    int u, k;
    std::cin >> u >> k;
    u--;
    for(int j=0; j<k; ++j) {
      int v;
      std::cin >> v;
      v--;
      G[u][v] = 1;
    }
  }

  for(int i=0; i<n; ++i) {
    for(int j=0; j<n; ++j) {
      if(j != n-1) std::cout << G[i][j] << " ";
      else std::cout << G[i][j];
    }
    std::cout << std::endl;
  }
}


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

int main() {
  int a, b, c, x;
  cin >> a >> b >> c >> x;

  int res = 0;
  for (int i = 0; i <= a; ++i) {
    for (int j = 0; j <= b; ++j) {
      int y = x - 500 * i - 100 * j;
      if (0 <= y && y / 50 <= c) {
        res++;
      }
    }
  }

  cout << res << endl;
}


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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    ll n,m;
    cin >> n >> m;
    vector<ll> a(n);
    for(i = 0;i < n;++i){
        cin >> a.at(i);
    }
    vector<ll> b(m);
    for(i = 0;i < m;++i){
        cin >> b.at(i);
    }
    const ll MOD = 1e9+7;
    sort(all(a));   sort(all(b));
    for(i = 0;i < n-1;++i){
        if(a.at(i) == a.at(i+1)){
            cout << 0 << endl;
            return 0;
        }
    }
    for(i = 0;i < m-1;++i){
        if(b.at(i) == b.at(i+1)){
            cout << 0 << endl;
            return 0;
        }
    }
    ll ans = 1;
    for(i = n*m;i >= 1;--i){
        ll indh = lower_bound(all(a), i) - a.begin();
        ll indw = lower_bound(all(b), i) - b.begin();
        if(indh == n || indw == m){
            cout << 0 << endl;
            return 0;
        }
        if(i == a.at(indh) && i == b.at(indw)) continue;
        else if(i == a.at(indh)){
            ll tmp = m - indw;
            ans *= tmp;
            ans %= MOD;
        }else if(i == b.at(indw)){
            ll tmp = n - indh;
            ans *= tmp;
            ans %= MOD;
        }else{
            ll tmp = (m - indw)*(n - indh);
            tmp -= n*m - i;
            if(tmp <= 0){
                cout << 0 << endl;
                return 0;
            }
            ans *= tmp;
            ans %= MOD;
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(){
  int N;
  cin >> N;
  char s[N];
for(int i=0;i<N;i++){
cin >> s[i];
}
int K;
cin >> K;
char r=s[K-1];
for(int i=0;i<N;i++){
if(s[i]!=r)
s[i]='*';
}
  for(int i=0;i<N;i++){
cout << s[i];
}
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#define MOD 1000000007

using namespace std;

int main() {
    int N,m;
    cin >> N;
    m = N;
    vector<char> a,b;
    while(N--){
        char x;
        scanf(" %c",&x);
        a.push_back(x);
    }
    N = m;
    while(N--){
        char x;
        scanf(" %c",&x);
        b.push_back(x);
    }
    long long ans = 0;
    int start = 1;
    int state = 0;
    if(a[0] == a[1]){
        start = 2;
        ans = 6;
        state = 1; //
    }else{
        ans = 3;
        state = 2; //
    }
    
    if(m==1){
        ans = 3;
        cout << ans << endl;
        return 0;
    }
    for(int i=start; i<m; i++){
        if(a[i] != b[i]){
            if(state == 2){
                ans = 2 * ans % MOD;
            }else{
                ans = 3 * ans % MOD;
            }
            state = 1;
            i++;
        }else{
            if(state == 2){
                ans = 2 * ans % MOD;
            }else{
                ans = ans;
            }
            state = 2;
        }
    }
    ans %= 1000000007;
    /*
    for(int i=0; i<m;i++){
        if(a[i] == i+1){
            Max++;
        }
        
    }*/
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256