akhauriyash/Code-Regression huggingface dataset:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n = int(ipt())
    ans = 0
    bmi = 10**18
    sm = 0
    for i in range(n):
        a,b = map(int,ipt().split())
        sm += a
        if a > b and bmi > b:
            bmi = b
    if bmi == 10**18:
        print(0)
    else:
        print(sm-bmi)

    return None

if __name__ == '__main__':
    main()


Measured memory_bytes: 75744
def agc023_a():
  n = int(input())
  A = list(map(int, input().split()))
  # 累積計算していき、通った地点と回数をカウント
  acc = 0
  transit = dict({0:1})
  for a in A:
    acc += a
    if transit.get(acc) == None:
      transit[acc] = 1
    else:
      transit[acc] += 1
  # 複数回通った地点どうしの区間の和は0
  # v個から2個選ぶ
  ans = 0
  for k, v in transit.items():
    if v >= 2:
      ans += v * (v-1) // 2
  print(ans)

agc023_a()

Measured memory_bytes: 39540
#include<bits/stdc++.h>
constexpr long long INFL = 1LL << 60;
constexpr int INF = 1e9;

using namespace std;

typedef long long ll;

int main()
{
    string s;
    cin >> s;
    if((s[0] == s[1] && s[1] == s[2]) || (s[1] == s[2] && s[2] == s[3]))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

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

public class Main {
	public static void main(String[] args) throws Exception {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

			String[] tmp = br.readLine().split(" ");
			int n = Integer.parseInt(tmp[0]);
			int m = Integer.parseInt(tmp[1]);

			List<List<Integer>> g = new ArrayList<>(n);
			for (int i = 0; i < n; i++) {
				g.add(new ArrayList<>());
			}

			for (int i = 0; i < m; i++) {
				tmp = br.readLine().split(" ");
				int a = Integer.parseInt(tmp[0]) - 1;
				int b = Integer.parseInt(tmp[1]) - 1;
				g.get(a).add(b);
				g.get(b).add(a);
			}

			int[] ans = new int[n];

			Queue<Integer> q = new ArrayDeque<>();
			q.offer(0);
			while (!q.isEmpty()) {
				int p = q.poll();
				for (int v : g.get(p)) {
					if (ans[v] == 0) {
						ans[v] = p + 1;
						q.add(v);
					}
				}
			}

			PrintWriter pw = new PrintWriter(System.out);
			pw.println("Yes");
			for (int i = 1; i < n; i++) {
				pw.println(ans[i]);
			}
			pw.flush();

		}
	}
}

Measured memory_bytes: 71956
N, Q = map(int, input().split())

edge = [[] for i in range(N)]
ans = [0] * N
query = [0] * N

for i in range(N-1):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

for q in range(Q):
    p, x = map(int, input().split())
    query[p-1] += x

is_visited = [False] * N
stack = [(0,0)]

while len(stack) != 0:
    cur, q = stack.pop()
    is_visited[cur] = True

    q = q + query[cur]
    ans[cur] += q

    for next in edge[cur]:
        if is_visited[next]:
            continue
        stack.append((next, q))

print(*ans)

Measured memory_bytes: 65772
#include<bits/stdc++.h>
#define ll long long
#define p 1000000007
using namespace std;
ll quick_mod(ll a, ll b)
{
    ll ans = 1;
    a %= p;
    while(b)
    {
        if(b & 1)
        {
            ans = ans * a % p;
            b--;
        }
        b >>= 1;
        a = a * a % p;
    }
    return ans;
}

ll C(ll n, ll m)
{
    if(m > n) return 0;
    ll ans = 1;
    for(int i=1; i<=m; i++)
    {
        ll a = (n + i - m) % p;
        ll b = i % p;
        ans = ans * (a * quick_mod(b, p-2) % p) % p;
    }
    return ans;
}

ll Lucas(ll n, ll m)
{
    if(m == 0) return 1;
    return C(n % p, m % p) * Lucas(n / p, m / p) % p;
}
int main()
{
    ll x,y,m,n;
    scanf("%lld%lld",&x,&y);
    if(2*x-y<0||2*y-x<0||(2*x-y)%3!=0||(2*y-x)%3!=0)
    {
        printf("0");
        return 0;
    }
    printf("%lld",Lucas((2*x-y)/3+(2*y-x)/3,(2*x-y)/3));
}


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

int main() {
    vector<vector<int>> bingo(3, vector<int>(3));
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> bingo[i][j];
        }
    }
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        int b;
        cin >> b;
        for (int i = 0; i < 3; i++) {
            replace(bingo.at(i).begin(), bingo.at(i).end(), b, -1);
        }
    }
    bool isb = false;
    if (bingo[0][0] == -1) {
        if ((bingo[0][1] == -1 && bingo[0][2] == -1) ||
            (bingo[1][0] == -1 && bingo[2][0] == -1) ||
            (bingo[1][1] == -1 && bingo[2][2] == -1)) {
                isb = true;
            }
    } else if  ((bingo[0][1] == -1 && bingo[1][1] == -1 && bingo[2][1] == -1) ||
                (bingo[0][2] == -1 && bingo[1][2] == -1 && bingo[2][2] == -1) ||
                (bingo[1][0] == -1 && bingo[1][1] == -1 && bingo[1][2] == -1) ||
                (bingo[2][0] == -1 && bingo[2][1] == -1 && bingo[2][2] == -1) ||
                (bingo[0][2] == -1 && bingo[1][1] == -1 && bingo[2][0] == -1)) {
                    isb = true;
                }
    cout << (isb ? "Yes" : "No") << endl;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define REP(i, n) for (int (i) = 0; (i) < (int)(n); i++) 
#define FOR(i, a, b) for(int (i) = a; (i) < (int)b; i++)
#define RREP(i, n) for(int (i)=((int)(n)-1); (i)>=0; i--)
#define RFOR(i, a, b) for(int (i) =((int)(b)-1); (i)>=(int)a; i--)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define NIL -1
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define SZ(x)  (int)x.size()
#define SP(x)  setprecision((int)x)


using namespace std ;
typedef long long ll;
using Graph = vector<vector<int>>;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef vector<string> vstr;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll LINF = 1e18;
const double EPS = 1e-9;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} //最大公約数
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} //最小公倍数

//-------------------------------------------------
// 
void yes(){
  cout <<"Yes"<<endl ;
}
void no(){
  cout <<"No"<<endl ;
}


//-------------------------------------------------
// メモ
/*






*/
//-------------------------------------------------


int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n ;
  cin >> n ;
  map<int,int> ma ;
  set<int> S ;
  REP(i,n){
    int a ;
    cin >> a ;
    ma[a]++ ;
    S.insert(a) ;
  }
  int ans = 0 ;
  
  auto itr = S.begin();
  while (itr != S.end()){
    if(ma[(*itr)]%2==1){
      ans++ ;
    }
    itr++;
  }
  
  cout << ans <<endl ;
  
  
  
  
  
  return 0 ;
}

Measured memory_bytes: 9600
a,b,c,d = list(map(int, input().split()))

def num_fact_in(begin, end):
    def f(div):
        return end//div - (begin-1)//div
    return f

import math
lcm = c * d // math.gcd(c, d)

f = num_fact_in(a, b)
print(b - a + 1 - (f(c) + f(d) - f(lcm)))

Measured memory_bytes: 9192
#include<cstdio>
#include<iostream>

using namespace std;
int main(){
    int N, M;
    cin >> N >> M;

    int ans = 0;
    ans += (N * (N - 1)) / 2;
    ans += (M * (M - 1)) / 2;

    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 256
n, a, b = map(int, input().split())
ans = 0

for i in range(1, n+1):
    digit_str_list = list(str(i))
    digit_int_list = [int(j) for j in digit_str_list]
    if sum(digit_int_list) >= a and sum(digit_int_list) <= b:
        ans += i

print(ans)

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

#define FOR(i, a, b) for(int i = a; i < b; i ++)
#define FORS(i, a, b, c) for(int i = a; i < b; i += c)
#define FORN(i, a, b) for(int i = a; i <= b; i ++)
#define FORD(i, a, b) for(int i = a-1; i >= b; i --)
#define FORE(i, b) for(auto &i:b)
#define REP(i, b) FOR(i, 0, b)
#define REPN(i, b) FORN(i, 0, b)
#define SQ(i) (i*i)
#define ALL(a) a.begin(), a.end()
#define ALLA(a,n) a, a+n
#define SORT(a) sort(ALL(a))
#define SORTA(a, n) sort(ALLA(a, n))
#define REV(a) reverse(ALL(a))
#define REVA(a, n) reverse(ALLA(a, n))
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define IN(a, b) (a.find(b) != a.end())
#define BACK(a) a.back(); a.RB()
#define QBACK(a) a.top(); a.pop()
#define PRINT(a) FORE(i, a) cout << i << " "; cout << endl

#define PB  push_back
#define RB  pop_back
#define RF  pop_front
#define INS insert
#define F   first
#define S   second
#define UM  unordered_map
#define US  unordered_set
#define PQ  priority_queue

#define IO ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<ll,ll> pll;
typedef queue<int> qi;
typedef queue<double> qd;
typedef queue<ll> qll;
typedef US<int> si;
typedef US<double> sd;
typedef US<ll> sll;
typedef vector<vi> mi;
typedef vector<vd> md;
typedef vector<vll> mll;
typedef vector<pi> vpi;
typedef vector<pd> vpd;
typedef vector<pll> vpll;

ll ans;

int main(){
  IO; string s; cin >> s;
  int N = s.size();
  vi occ(2019); occ[0] ++;
  int m = 0;
  int p = 1;
  FORD(i, N, 0){
    m += p*(s[i]-'0'); m %= 2019; p = p*10%2019;
    ans += occ[m]++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 3752
n = int(input())
s = input()
e_l, e_sum = [], 0
w_l, w_sum = [], 0
for i in range(n):
    if s[i] == 'E':
        e_sum += 1
    else:
        w_sum += 1
    e_l.append(e_sum)
    w_l.append(w_sum)
for i in range(n):
    if i == 0:
        ans = e_l[n-1] - e_l[0]
    elif i == n:
        ans = max(ans, w_l[n-2])
    else:
        ans = min(ans, e_l[n-1] - e_l[i] + w_l[i-1])
print(ans)

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

typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
#define f first
#define s second
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0)
#define int ll
int N,M,X;
int C[13];
int A[14][14];
int ans = 1e9;

int32_t main(){
	fast;
	
	cin>>N>>M>>X;
	
	FOR(i,0,N-1){
		cin>>C[i];
		
		FOR(j,0,M-1){
			cin>>A[i][j];
		}
	}
	
	FOR(bm,0,(1<<N) - 1){
		
		int num[15];
		FOR(i,0,M-1) num[i] = 0;
		int res = 0;
		
		
		FOR(i,0,N-1){
			if (bm & (1<<i)){
				FOR(j,0,M-1){
					num[j] += A[i][j];
				}
				res += C[i];
			}
		}
		bool yes = 1;
		FOR(i,0,M-1){
			if (num[i] < X) yes = 0;
		}
		if (yes) ans = min(ans,res);
	}
	if (ans == 1e9) cout<<-1;
	else cout<<ans;
}


Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Edge = pair<int, int>;
using Graph = vector<vector<Edge>>;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
const ll MOD = 1000000007;
const ll nmax = 8;
const ll INF = 1e9;
bool graph[nmax][nmax];
vector<vector<ll>> dist = vector<vector<ll>>(nmax, vector<ll>(nmax, INF));
void warshall_floyd(ll n)
{
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            for (size_t k = 0; k < n; k++)
            {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }
}

class UnionFind
{
  public:
    vector<ll> Parent;

    UnionFind(ll N)
    {
        Parent = vector<ll>(N, -1);
    }
    ll find(ll A)
    {
        if (Parent[A] < 0)
            return A;
        return Parent[A] = find(Parent[A]);
    }

    ll size(ll A)
    {
        return -Parent[find(A)];
    }

    bool Union(ll A, ll B)
    {
        A = find(A);
        B = find(B);
        if (A == B)
        {
            return false;
        }
        if (size(A) < size(B))
            swap(A, B);

        Parent[A] += Parent[B];
        Parent[B] = A;

        return true;
    }
};

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

ll lcm(ll a, ll b)
{
    ll g = gcd(a, b);
    return a / g * b;
}

ll mulMod(ll a, ll b)
{
    return (((a % MOD) * (b % MOD)) % MOD);
}

ll powMod(ll a, ll p)
{
    if (p == 0)
    {
        return 1;
    }
    else if (p % 2 == 0)
    {
        ll half = powMod(a, p / 2);
        return mulMod(half, half);
    }
    else
    {
        return mulMod(powMod(a, p - 1), a);
    }
}

ll ceil(ll a, ll b)
{
    return (a + b - 1) / b;
}


void solve(long long A, long long B){
    int plus,minus,mul;
    plus = A+B;
    minus = A-B;
    mul = A*B;
    cout << max(max(plus,minus),mul) <<endl;
}

int main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    solve(A, B);
    return 0;
}


Measured memory_bytes: 256
N,M=map(int,input().split())


m=2**M
ans=0
i=1
while True:
        k=( (1*((1/m))) * ((( (m-1)/m)**(i-1)) )) * ( 1900*M*i +(N-M)*100*i)#       +( (1*((1/m))) * ((( (m-1)/m)**(i-1)) )) *
        ans+=k
        i+=1
        if(i>10000):
                break

print(int(ans+0.5))

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

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

ll N;
vector<ll> A;

int main() {
    cin >> N;
    A.resize(N);

    rep(i, N) cin >> A[i];

    ll S = 0;
    rep(i, N) S += A[i];

    vector<ll> x(N);
    x[0] = S;
    for (ll i = 2; i <= N - 1; i += 2) {
        x[0] -= 2 * A[i - 1];
    }

    for (ll i = 1; i < N; i++) {
        x[i] = 2 * A[i - 1] - x[i - 1];
    }

    rep(i, N) {
        cout << x[i] << " ";
    }
    cout << endl;
}

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

using namespace std;


#define MAXN 51
typedef long long ll;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll n, k, x[MAXN], y[MAXN], ans = 4e18+1;
  vector <ll> h, v;
  cin >> n >> k;
  for (int i = 0; i < n; ++i) {
    cin >> x[i] >> y[i];
    h.push_back(x[i]);
    v.push_back(y[i]);
  }
  sort(h.begin(), h.end());
  sort(v.begin(), v.end());
  h.resize(unique(h.begin(), h.end())-h.begin());
  v.resize(unique(v.begin(), v.end())-v.begin());
  for (int h1 = 0; h1 < h.size(); ++h1) {
    for (int h2 = h1; h2 < h.size(); ++h2) {
      for (int v1 = 0; v1 < v.size(); ++v1) {
        for (int v2 = v1; v2 < v.size(); ++v2) {
          int cnt = 0;
          for (int i = 0; i < n; ++i) {
            cnt += (h[h1]<=x[i] && x[i]<=h[h2] && v[v1]<=y[i] && y[i]<=v[v2]);
          }
          if (cnt>=k) {
            ans = min(ans, (h[h2]-h[h1])*(v[v2]-v[v1]));
          }
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>

//#include <tuple>

//#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define ll long long
#define pb push_back

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  int ans = b/a;
  if (ans < c){
    cout << ans << endl;
  } else {
    cout << c << endl;
  }
  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<n;i++)
const long long MOD = 1e9+7;
using namespace std;
typedef pair<int,int> pii;
int main(){
    int a,b;
    cin >> a >> b;
    rep(i,max(a,b)) cout << min(a,b);
    cout << endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
  int c[3][3];
  for(int i = 0; i<3 ;i++){
    for(int j = 0; j<3 ;j++){
      cin >> c[i][j];
    }
  }
  if(c[0][0] - c[0][1] == c[1][0] - c[1][1] &&
     c[0][0] - c[0][1] == c[2][0] - c[2][1] &&
     c[0][1] - c[0][2] == c[1][1] - c[1][2] &&
     c[0][1] - c[0][2] == c[2][1] - c[2][2]
   ){
     cout << "Yes" << endl;
   }else{
     cout << "No" << endl;
   }
   return 0;
 }


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define MOD 1000000007
#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL) 

int32_t main() {
    fast_io;
 
    int n;
    cin >> n;
    int change = 1000 - (n % 1000);
    if (change == 1000) {
        change = 0;
    }
    cout << change << endl;

    return 0;
}

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

int main() {
    int x, y; cin >> x >> y;
    int ans;
    if (x <= y && (0 <= x || y <= 0)) ans = y - x;
    else if (y < x && (0 < y || x < 0)) ans = x - y + 2;
    else ans = abs(abs(x) - abs(y)) + 1;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int A1 = sc.nextInt();
      	int A2 = sc.nextInt();
      	int A3 = sc.nextInt();
      	if(A1 + A2 + A3 >= 22){
		        System.out.println("bust");          
        }else{
          		System.out.println("win");
        }
    }
}

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


// type definitions
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< vi > vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef complex<int> ci;
typedef complex<double> cd;
typedef complex<long double> cld;

// macros
#define rep(i, a, b) for(int i=a; i<b; i++)
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define all(c) c.begin(), c.end()
#define tr(c, it) for(auto it=(c).begin(); it!=c.end(); it++)
#define pb push_back
#define mp make_pair
#define bitcount __builtin_popcount
#define ispresent(c, x) ((c).find(x) != (c).end())
#define watch(x) cout<< (#x) << " is " << (x) <<"\n";
#define sz(x) ((int)((x).size()))
#define UNIQUE(c) (c).resize(unique(all(c)) - (c).begin())
#define pii2ll(p) ((ll)(p).first<<32 | (p).second)

// template functions
template <typename T>
inline void printV(vector<T>& a) { rep(i, 0, sz(a)) { cout<<a[i]<<" "; } cout<<"\n"; }
template <typename T>
inline void printV(vector<T>& a, int n) { rep(i, 0, n) { cout<<a[i]<<" "; } cout<<"\n"; }
template <typename T>
inline void printVV(vector<vector<T>>& a)
{
	rep(i, 0, sz(a)) {
		printV(a[i]);
	}
	cout<<"\n";
}

template <typename T>
inline void clearVV(vector<vector<T>>& a)
{
	for(auto& x:a) {
		x.clear();
	}
	a.clear();
}
template <typename T>
inline void assignVV(vector<vector<T>> &a, T val)
{
	for(int i=0; i<sz(a); i++) {
		for(int j=0; j<sz(a[i]); j++) {
			a[i][j]=val;
		}
	}
}


// constants
const long double eps = 1e-9;
const int inf = 5e8;
const int modn = 1e9+7;
const int MAX = 1e5;

typedef long double ld;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // Your code here
    cout<<fixed<<setprecision(10);
	int n;
	cin>>n;
	vector<ld> p(n+1);
	rep(i,0, n) cin>>p[i];
	vector<vector<ld>> dp(n+1, vector<ld>(n+1));
	assignVV(dp, (ld)-1);
	
	function<ld(int, int)> solve=[&](int i, int no)
	{
		if(i>n-1) {
			if(no<=0) return (ld)1;
			else return (ld)0;
		}
		if(no<=0) return (ld)1;
		if(no>n-i+1) return (ld)0;
		
		if(fabs(dp[i][no]+1)>eps) return dp[i][no];
		ld &memo=dp[i][no];
		memo=p[i]*solve(i+1, no-1);
		memo+=(1-p[i])*solve(i+1, no);
		return memo;
	};
	cout<<solve(0, n/2+1)<<"\n";
	//~ printVV(dp);
    return 0;
}



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

string solve(int a, int b)
{
    if (a <= 0 && 0 <= b) return "Zero";
    if (0 < a) return "Positive";
    auto difference = b-a+1;
    return difference % 2 ? "Negative" : "Positive";
}

int main()
{
    int a, b; cin >> a >> b;
    cout << solve(a, b) << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("-ffloat-store")
 
#define int  long long
#define rep(i,begin,end) for(__typeof(end)i=(begin)-((begin)>(end));i!=(end)-((begin)>(end));i+=1-2*((begin)>(end)))
#define F first
#define S second
#define sz(x) ((int)x.size())
#define pb push_back
#define pf push_front
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define mod 1000000007
#define what_is(x) cerr << #x << " is " << x <<"\n";
#define sortA(v) sort(v.begin(), v.end())
#define sortD(v) sort(v.rbegin(), v.rend())
#define PI 3.14159265358979323846
#define vout(a) for(auto x:a) cout<<x<<" ";
#define INF 2000000000000000000 //1e16
 
// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
 
 
// using namespace __gnu_pbds;
using namespace std;
 
using ll  = long long;
using vi  = vector<int>;
using vvi = vector<vi>;
using pii = pair<int,int>;
using vii = vector<pii>;
using mi  = multiset<int>;
using mii = multiset<pii>;
 
int lcm(int a,int b) {return (a*(b/__gcd(a,b)));}



void solve()
{
    int n,m,t,i,k,r,l,u,v,w,j,pos,sum=0,flag=0,count=0;
    string S,T; 
    // int x1,y1,x2,y2,z1,z2;
    cin>>n;
    vi a(n);
    rep(i,0,n) cin>>a[i];
    int mn=a[0];
    int ans=0;
    rep(i,1,n)
    {
        if(a[i]<mn)
        {
            ans+=mn-a[i];
        }
        else
        {
            mn=a[i];
        }
    }
    cout<<ans;
}


signed main()
{
    #ifndef ONLINE_JUDGE 
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
    #endif
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)
    {
        solve();
        if(t)cout<<"\n";
    }
    return 0;
}

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

bool isACGT(char c){
    string table = "ACGT";
    if(table.find(c)!=string::npos){
        return true;
    }else{
        return false;
    }
}

int main(){
    string S;
    cin >> S;
    int maxlen = 0;
    int cnt = 0;
    for(int i=0;i<S.length();i++){
        if(isACGT(S[i])){
            cnt++;
        }else{
            maxlen=max(maxlen,cnt);
            cnt=0;
        }
    }
    maxlen=max(maxlen,cnt);
    cout << maxlen << endl;
    return 0;
}

Measured memory_bytes: 256
from itertools import accumulate 
#acumulate [a[0], a[0]+a[1], a[0]+...]
 
n, k = map(int, input().split())
p = [int(x) - 1 for x in input().split()]
c = list(map(int, input().split()))
ans = -(10 ** 18)
 
for i in range(n):
    pos = i
    scores = []
    while True:
        pos = p[pos]
        scores.append(c[pos])
        if pos == i:
            break
    m = len(scores)
    s = list(accumulate(scores))
    for j in range(min(m, k)):
        x = (k - j - 1) // m
        ans = max(ans, s[j], s[j] + s[-1] * x)
 
print(ans)

Measured memory_bytes: 103532
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stdio.h>
using namespace std;
map <int ,int> mpa,mpb;

int top, S[1000];

void push(int x){
  S[++top]=x;
}

int pop(){
  top--;
  return S[top+1];
}

int main (){
  int a,b;
  top=0;
  char s[100];
  while(scanf("%s", s ) !=EOF){
    if(s[0]=='+'){
      b=pop();
      a=pop();
      push(a+b);
    }
    else if(s[0]=='-'){
      b=pop();
      a=pop();
      push(a-b);
    }
    else if(s[0]=='*'){
      b=pop();
      a=pop();
      push(a*b);
    }
    else{
      push(atoi(s));
    }
  }
  printf("%d\n", pop());
  return 0;
}


Measured memory_bytes: 3224
s=list(input())

count=0
max_=0
for i in range(len(s)):
  if s[i]=='A' or s[i]=='C' or s[i]=='G' or s[i]=='T':
    count+=1
  else:
    count=0
  if max_<count:
      max_=count
print(max_)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
typedef vector<int> vi;
typedef vector<ll> vll;
 
#define  ff     first
#define  ss     second
#define  pb     push_back
#define  all(x) (x).begin(), (x).end()
#define  rep(i,a,b) for(int i=a ; i<b ; ++i)
#define  deb(x) cout << #x << " - " << x << "\n";
#define  IOS    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define  D2(x)  cout << "[" << #x << ": "; for(auto it:x) cout << it << " "; cout << "]\n"; 
#define  D2p(x)	cout << #x << " ~ [ "; for(auto n: x) cout << n.first << "-" << n.second << " / "; cout << "]" << "\n";
#define  ps(x,y) fixed<<setprecision(y)<<x
 
#define PI 3.141592653589793238462643383279502884L
const ll MOD = 1e9 + 7;
const ll INF = 1000000000;
const ll MAX_N = 1e5 + 2;

int main() {
    IOS;
    ll a; cin>> a;
    a = a+ a*a + a*a*a;
    cout << a;
}

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

#define CIN1(a) long long a;cin >> a;
#define CIN2(a,b) long long a,b;cin >> a >> b;
#define CIN3(a,b,c) long long a,b,c;cin >> a >> b >> c;
#define rep(i,n) for(int i=0,i##_len=(n); i<i##_len; ++i)

int main(){
    string s;cin >> s;
    int a = stoi(s.substr(0,2));
    int b = stoi(s.substr(2,2));

    string ans;
    if(1<=a && a<=12){
        if(1<=b && b<=12) ans = "AMBIGUOUS";
        else ans = "MMYY";
    }else{
        if(1<=b && b<=12) ans = "YYMM";
        else ans = "NA";
    }
    cout << ans << endl;
}





Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(final String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int n = scanner.nextInt();
        final int m = scanner.nextInt();

        System.out.println(((n - m) * 100 + m * 1900) * (int) Math.pow(2, m));
    }
}


Measured memory_bytes: 21716
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import static java.lang.Integer.parseInt;

/**
 * Change of the Era Name
 */
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;
		String[] words;

		while ((line = br.readLine()) != null && !line.isEmpty()) {

			if (line.equals("#")) break;

			words = line.split(" ");

			int y, m;
			y = parseInt(words[1]);
			m = parseInt(words[2]);

			if (y < 31 || (y <= 31 && m <= 4)) {
				System.out.println(line);
			} else {
				y -= 30;
				System.out.printf("%s %d %s %s%n", "?", y, words[2], words[3]);
			}
		}
	}
}


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

int main(){
	string s,t;
	cin >> s >>t;
	bool f=true;
	for(int i=0; i < s.size(); i++){
		if(s[i] != t[i]) f = false;
	}
	if (f) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


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

int main(){
    int h, w;
    for(;;){
        cin >> h >> w;
        if(h == 0 && w == 0) break;
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++) cout << '#';
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3092
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
#include<set>
#include<climits>
#include<cstdlib>
#include<cmath>
#include<string>

using namespace std;

#define INF 1 << 29
#define LL long long int

LL const MOD = 1000000007;


struct edge{int to; long long int cap; int rev;};

class Edmonds_Karp{
    int source;
    int sink;
    int v;
    long long int maxflow = 10000000000;
    std::vector<std::vector<edge>> g;
    std::vector<std::pair<int,int>> back_v;
    std::vector<bool> used;
    std::stack<std::pair<int,int>> minimum_route;

    bool BFS(){
        std::queue<int> que;

        que.push(source);

        while(!que.empty()){
            int t = que.front();
            que.pop();

            if(t == sink)return true;

            if(used[t])continue;

            used[t] = true;

            for(int i = 0; i < g[t].size(); i++){
                if(!used[g[t][i].to] && g[t][i].cap > 0){
                    que.push(g[t][i].to);
                    back_v[g[t][i].to] = std::make_pair(t,i);
                }
            }
        }

        return false;
    }

    void backtrack(){
        minimum_route.push(back_v[sink]);
        std::pair<int,int> t = back_v[sink];
        while(t.second >= 0){
            minimum_route.push(t);
            t = back_v[t.first];
        }
    }

    long long int DFS(int s,long long int f){
        if(s == sink) return f;

        std::pair<int,int> t = minimum_route.top();
        minimum_route.pop();

        edge &e = g[s][t.second];
        
        int ret = DFS(e.to,std::min(f,e.cap));
        if(ret < 0) return ret;

        e.cap -= ret;
        g[e.to][e.rev].cap += ret;

        return ret;
    }
    
    public:
    Edmonds_Karp(int s,int t,int n):source(s),sink(t),v(n){
        g = std::vector<std::vector<edge>>(v+1);
        back_v = std::vector<std::pair<int,int>>(v+1,std::make_pair(-1,-1));
        used = std::vector<bool>(v+1,false);
    }

    void add_edge(int f,int t,long long int c){
        g[f].push_back(edge{t,c,(int)g[t].size()});
        g[t].push_back(edge{f,0,(int)g[f].size()-1});
    }

    long long int solve(){
        long long int ans = 0;

        while(BFS()){
            backtrack();
            ans += DFS(source,maxflow);
            fill(used.begin(),used.end(),false);
            fill(back_v.begin(),back_v.end(),std::make_pair(-1,-1));
        }

        return ans;
    }
};


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

    LL n;
    cin >> n;

    vector<LL> a(n+1);

    for(int i = 1; i < n+1; i++){
        cin >> a[i];
    }

    Edmonds_Karp ek = Edmonds_Karp(0,n+1,n+1);

    LL ans = 0;

    for(int i = 1; i < n+1; i++){
        if(a[i] < 0){
            ek.add_edge(0,i,abs(a[i]));
        }else{
            ek.add_edge(i,n+1,abs(a[i]));
            ans += a[i];
        }
        for(int j = i*2; j < n+1; j += i){
            ek.add_edge(i,j,1333333333333);
        }
    }

    cout << ans - ek.solve() << endl;
    
    return 0;
}

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

public class Main{
	final static int MOD = 1000000007;
	final static int INF = 1000000000;

	public static void main(String[] args) throws IOException{
		NScanner sc = new NScanner(System.in);
		int n = sc.nextInt();
		for(int i = 1; i <= n; ++i){
			if(i % 3 == 0)
				System.out.printf(" %d", i);
			else{
				int x = i;
				while(x > 0){
					if(x % 10 == 3){
						System.out.printf(" %d", i); break;
					}
					x /= 10;
				}
			}
		}
		System.out.println();
	}

}

class NScanner{

	private BufferedReader br;
	private StringTokenizer tok;

	public NScanner(InputStream is) throws IOException{
		br = new BufferedReader(new InputStreamReader(is));
		getLine();
	}

	private void getLine() throws IOException{
		while(tok == null || !hasNext()){
			tok = new StringTokenizer(br.readLine());
		}
	}

	private boolean hasNext(){
		return tok.hasMoreTokens();
	}

	public String next() throws IOException{
		if(hasNext()){
			return tok.nextToken();
		}else{
			getLine();
			return tok.nextToken();
		}
	}

	public int nextInt() throws IOException{
		if(hasNext()){
			return Integer.parseInt(tok.nextToken());
		}else{
			getLine();
			return Integer.parseInt(tok.nextToken());
		}
	}

	public long nextLong() throws IOException{
		if(hasNext()){
			return Long.parseLong(tok.nextToken());
		}else{
			getLine();
			return Long.parseLong(tok.nextToken());
		}
	}

	public double nextDouble() throws IOException{
		if(hasNext()){
			return Double.parseDouble(tok.nextToken());
		}else{
			getLine();
			return Double.parseDouble(tok.nextToken());
		}
	}
}


Measured memory_bytes: 35540
import sys
N = int(input())
S = input()

ans = 0
W = -1
for i in range(N):
    if S[i] == "W":
        W = i
        break
if W == -1:
    print(ans)
    sys.exit()

R = N
for i in range(N-1,-1,-1):
    if S[i] == "R":
        R = i
        break
if R == N:
    print(ans)
    sys.exit()

if(R<=W):
    print(ans)
    sys.exit()

ans += 1

while True:
    flagW = False
    flagR = False

    for i in range(W+1,R):
        if S[i] == "W":
            W = i
            flagW = True
            break
    
    for j in range(R-1, W, -1):
        if S[j] == "R":
            R = j
            flagR = True
            break
    
    if flagW and flagR:
        ans += 1
        continue
    else:
        print(ans)
        sys.exit()

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

int main() {
  
  int64_t X, Y; cin >> X >> Y;
  
  int ans = 1; int64_t tmp = X;
  
  while (true) {
    
    tmp *= 2;
    
    if (tmp <= Y) ans++;
    
    else break;
    
  }
  
  cout << ans << endl;
  
}

Measured memory_bytes: 256
#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 ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> pip;
const ll INF = 1ll<<29;
const ll MOD = 1000000007;
const double EPS = 1e-9;
const bool debug = 0;
//---------------------------------//

struct edge {int to, cap, rev; };

int H, W;
string maps[100];
vector<edge> g[20000];
bool done[20000];

void add_edge(int from, int to, int cap) {
	g[from].push_back((edge){ to, cap, g[to].size() });
	g[to].push_back((edge){ from, 0, g[from].size() - 1});
}

int dfs(int v, int t, int f) {
	if (v == t) return f;
	done[v] = true;
	
	REP(i, g[v].size()) {
		edge &e = g[v][i];
		
		if (!done[e.to] && e.cap > 0) {
			int d = dfs(e.to, t, min(f, e.cap));
			if (d > 0) {
				e.cap -= d;
				g[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
	
	return 0;
}

int max_flow(int s, int t) {
	int res = 0;
	while (true) {
		memset(done, 0, sizeof(done));
		int flow = dfs(s, t, INF);
		if (!flow) break;
		res += flow;
	}
	return res;
}

int main() {
	cin >> H >> W;
	REP(i, H) cin >> maps[i];
	
	int st, et;
	REP(i, H) REP(j, W) {
		if (maps[i][j] == 'S') {
			st = i * W + j;
			maps[i][j] = 'o';
		}
		if (maps[i][j] == 'T') {
			et = i * W + j;
			maps[i][j] = 'o';
		}
	}
	
	vector<int> cx[100], cy[100];
	REP(i, H) REP(j, W) {
		if (maps[i][j] == 'o') {
			cy[i].push_back(i * W + j);
			cx[j].push_back(i * W + j);
			add_edge(i * W + j, i * W + j + 10000, 1);
		}
	}
	
	REP(i, H) {
		REP(j, cy[i].size()) {
			REP(k, cy[i].size()) {
				if (j == k) continue;
				add_edge(cy[i][j] + 10000, cy[i][k], 1);
			}
		}
	}
	
	REP(i, W) {
		REP(j, cx[i].size()) {
			REP(k, cx[i].size()) {
				if (j == k) continue;
				add_edge(cx[i][j] + 10000, cx[i][k], 1);
			}
		}
	}
	
	if (st / W == et / W || st % W == et % W) puts("-1");
	else cout << max_flow(st + 10000, et) << endl;
	
	return 0;
}


Measured memory_bytes: 63360
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <numeric>
#include <functional>
#include <array>
#include <map>
#include <set>

#define INF /*1000000007*/ 1000000000000000003
#define MOD 1000000007

using namespace std;
using P = pair<int, long long>;
using T = tuple<int, int, int>;
using edge = struct { int to; long long dist; };

vector<edge>tree[100010];
vector<P> connect[100005];
long long cost[100005];

bool compare_by_second(pair<int, int> a, pair<int, int> b) {
	if (a.second != b.second) {
		return a.second < b.second;
	}
	else {
		return a.first < b.first;
	}
}

int main() {

	int N;
	cin >> N;

	double a, b;
	if (N % 2 == 0) {
		a = N / 2;
	}
	else {
		a = N / 2 + 1;
	}

	double ans = a / (double)N;
	printf("%.10lf\n", ans);
}


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

d = {}
for i in range(n):
    if a[i] in d:
        d[a[i]] += 1
    else:
        d[a[i]] = 1

if len(d.keys()) <= k:
    print(0)
else:
    a = list(d.values())
    b = sorted(d.values())[-k:]
    for i in b:
        if i in a:
            a.remove(i)
    print(sum(a))


Measured memory_bytes: 34004
import java.util.Scanner;

public class Main {


	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String in1 = sc.nextLine();
		String[] inArray = in1.split(" ");

		int isu = Integer.parseInt(inArray[0]);
		int hito = Integer.parseInt(inArray[1]);
		int haba = Integer.parseInt(inArray[2]);

		int start = isu - haba;
		int ans = start / (hito + haba);

		System.out.println(ans);

	}


}

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

using namespace std;

string s;

bool exists2(int l, int r) {
    for (int i = l; i < r; i++) {
        if (s[i] == '#' && s[i + 1] == '#') {
            return true;
        }
    }
    return false;
}

int main() {
    int N, A, B, C, D;
    cin >> N >> A >> B >> C >> D;
    cin >> s;
    s = '.' + s + '.';

    if (exists2(A, C) or exists2(B, D)) {
        cout << "No" << endl;
        return 0;
    }

    if (C < D) {
        cout << "Yes" << endl;
        return 0;
    }

    for (int i = B; i <= D; i++) {
        if (s[i - 1] == '.' && s[i] == '.' && s[i + 1] == '.') {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 772
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
INF = 10 ** 9 + 7

D = defaultdict(int)
for a in A:
    for i in range(61):
        # a の i ビット目がたっているか否か
        D[1 << i] += bool(a & (1 << i))

ans = 0
for key, value in D.items():
    ans += key * value * (N - value)
    ans %= INF

print(ans % INF)

Measured memory_bytes: 124028
#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>
#include <numeric>
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; }

constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int inf = 1 << 28;
//constexpr long long mod = 1000000007LL;
//constexpr long long mod = 998244353LL;

using namespace std;
typedef unsigned long long ull;
typedef long long ll;


int main()
{
	/*
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	*/

	int kkt; scanf("%d", &kkt);
	string s; cin >> s;
	int left = kkt;
	int right = -1;
	for (int i = 0; i < kkt; i++) {
		if (s[i] == '>') chmin(left, i);
		else if(s[i] == '<') chmax(right, i);
	}
	int res = 0;
	if (left != -1) chmax(res, kkt - left);
	if (right != kkt) chmax(res, right + 1);
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 3420
use std::io::Read;

fn main() {
    let mut buf = String::new();

    std::io::stdin().read_to_string(&mut buf).unwrap();

    let mut iter = buf.split_whitespace();
    let s: Vec<char> = iter.next().unwrap().chars().collect();

    let mut ans = true;

    for i in 0..s.len() {
        // println!("{}", s[i]);
        if i % 2 == 0 {
            if s[i] == 'L' {
                ans = false;
                break;
            }
        } else if i % 2 == 1 {
            if s[i] == 'R' {
                ans = false;
                break;
            }
        }
        // println!("{}", i);
    }

    println!("{}", if ans { "Yes" } else { "No" });
}


Measured memory_bytes: 4352
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
#include<map>
#include<set>
#define MOD 1000000007
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
void init_io(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(10);
}
signed main(){
  init_io();
  ll dp[110][4][4][4]={};
  ll n;
  cin >> n;
  for(int i=0;i<4;i++){
    for(int j=0;j<4;j++){
      for(int k=0;k<4;k++){
        dp[2][i][j][k] = 1;
      }
    }
  }
  dp[2][0][2][1] = dp[2][0][1][2] = dp[2][1][0][2] = 0;
  for(int i=3;i<n;i++){
    for(int j=0;j<4;j++){
      for(int k=0;k<4;k++){
        ll sum = 0,ssum=0;
        for(int l=0;l<4;l++){
          sum += dp[i-1][l][j][k];
          sum %= MOD;
          if(!(l==0&&(k==1||j==1))){
            ssum += dp[i-1][l][j][k];
            ssum %= MOD;
          }
        }
        for(int l=0;l<4;l++){
          dp[i][j][k][l] = sum;
        }
        dp[i][j][k][2] = ssum;
      }
    }
    dp[i][0][2][1] = dp[i][0][1][2] = dp[i][1][0][2] = 0;
  }
  ll ans =0;
  for(int i=0;i<4;i++){
    for(int j=0;j<4;j++){
      for(int k=0;k<4;k++){
        ans += dp[n-1][i][j][k];
        ans %= MOD;
      }
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
using namespace std;
char t[512];
int k,u,p,c;
int main(){
	scanf("%s",t);
	for(int i=0;t[i];i++){
		if(t[i]=='K')k++;
		if(t[i]=='U')u++;
		if(t[i]=='P')p++;
		if(t[i]=='C')c++;
	}
	printf("%d\n",min(min(k,u),min(p,c)));
}

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

void calc(ll j, int ii) {
	if (ii == 0)
	{
		c++;
		if (c == k)
		{
			cout << j << endl;
			exit(0);
		}
		return;
	}
	ll i = j * 10;
	j %= 10;
	if (j > 0)
		calc(i + j - 1, ii - 1);
	calc(i + j, ii - 1);
	if (j < 9)
		calc(i + j + 1, ii - 1);
}

int		main(void)
{
	cin >> k;
	int ii = 0;
	ll j;
	while (++ii) // ii; 桁数
		for (j = 1; j <= 9; j++)
			calc(j, ii - 1);
	return (0);
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void){
int n,a[300];
scanf("%d",&n);
//scanf("%d",&n);
for(int count=0;count<n;count++){
scanf("%d",&a[count]);
}
/*for(int count=0;count<n;count++){
scanf("%d",&a[count]);
}
*/
for(int count2=0;;count2++){
for(int count=0;count<n;count++){
if(a[count]%2!=0){printf("%d",count2);return 0;}
else{a[count]=a[count]/2;}
}

}
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int i,j,N,sum1,sum2,minn,T;
    T = 1;
    
    cin >> N;
    vector<int> vec(N);
    for(i = 0;i < N;i++){
        cin >> vec.at(i);
    }
    
    for(i = 0;i < N;i++){
        sum1 = sum2 = 0;
        
        for(j = 0;j < T;j++){
            sum1 += vec.at(j);
        }
        for(j = T;j < N;j++){
            sum2 += vec.at(j);
        }
        if(T==1){
            minn = abs(sum1-sum2);
        }
        minn = min(minn,abs(sum1-sum2));
        T++;
    }
    
    cout << minn << endl;
}

Measured memory_bytes: 256
//Akash Kumar Mondol
//Department of ICE,University of Rajshahi,Bangladesh
#include<bits/stdc++.h>
using namespace std;
#define pr(x) cerr << "\n" << (#x) << " is " << (x) << endl
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define scd(x) scanf("%lf",&x)
#define pfi(x) printf("%d",x)
#define pfl(x) printf("%lld",x)
#define pfd(x) printf("%lf",x)
#define pfc(x) printf("Case %d: ",x)
#define ps printf(" ")
#define pn printf("\n")
#define mod 1000000007
#define Toggle(n,i) (n^(1<<i))
#define Check(n,i) (n&(1<<i))
#define Set(n,i) (n|(1<<i))
#define Reset(n,i) (n&(~(1<<i)))
//#define valid(nx,ny) nx>=0&& nx<r && ny>=0 && ny<c
//memset(a, 0, sizeof(a));
//freopen("file_name.txt","read_or_write",stdout_or_stdin);
int main()
{
    //freopen("file_name.txt","w",stdout);
    //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int a,b,c;
    cin>>a>>b>>c;
    int d=a-b;
    int ans=c-d;
    if(ans<0)
    {
        cout<<"0\n";
    }
    else
        cout<<ans<<endl;
    return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
#include <limits>


int64_t getAllPattyNumber(const int64_t l) {
	int64_t result = 1L;
	for (int64_t i = 0; i < l + 1; ++i) {
		result *= 2L;
	}
	return result - 1;
//	return std::pow(2, l + 1) - 1;
}

int64_t getAllLayerNumber(const int64_t l) {
	int64_t result = 1L;
	for (int64_t i = 0; i < l + 2; ++i) {
		result *= 2L;
	}
	return result - 3;
	//	return std::pow(2, l + 2) - 3;
}

int64_t getPattyNumber(const int64_t n, const int64_t x) {
	const auto current_all_layer_number = getAllLayerNumber(n);
	if (current_all_layer_number < x) {
		return -1;
	}
	if (n == 0) {
		return 1;
	}
	if (x == 1) {
		// first one is bans if n > 0
		return 0;
	}
	if (x == current_all_layer_number) {
		return getAllPattyNumber(n);
	}
	const auto previous_patty_number = getAllPattyNumber(n - 1);
	if (x == (current_all_layer_number + 1) / 2) {
		return previous_patty_number + 1;
	}
	if (x < (current_all_layer_number + 1) / 2) {
		return getPattyNumber(n - 1, x - 1);
	}
	else {
		return previous_patty_number + 1 +
			getPattyNumber(n - 1, x - (current_all_layer_number + 1) / 2);
	}
}
int main() {
	int64_t n, x;
	std::cin >> n >> x;
	std::cout << getPattyNumber(n, x) << std::endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
	int  A,B,C,D,E,F,suger,suger1=0,water,a,b,c,d,sum,sum1=0;
	double e,m=0;
	cin>>A>>B>>C>>D>>E>>F;
	for(a=0;a*A*100<=F;a++)
	{
		for(b=0;b*B*100+a*A*100<=F;b++)
		{
			for(c=0;c*C+b*B*100+a*A*100<=F;c++)
			{
				for(d=0;d*D+c*C+b*B*100+a*A*100<=F;d++)
				{
					suger=c*C+d*D;
					water=a*A*100+b*B*100;
					sum=suger+water;
					if((a*A+b*B)*E<suger ||sum==0) continue;
					e=100.0*suger/sum;
					if(e>=m)
					{
						m=e;
						suger1=suger;
						sum1=sum;
					}
				}
			}
		}
	}
	cout<<sum1<<" "<<suger1<<endl;
	return 0;
}

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

using namespace std;

int idx,S;

bool parse(const string &s){
  if(idx == (int)s.size()) return true;
  idx++;
  bool l,r,res;
  switch(s[idx]){
  case 'T':
    return true;
  case 'F':
    return false;
  case '-':
    return !parse(s);
  case '(':
    l = parse(s);
    idx++;
    if(s[idx] == '+'){
      r = parse(s);
      res = l | r;
    }else if(s[idx] == '*'){
      r = parse(s);
      res = l & r; 
    }else{
      idx++;
      r = parse(s);
      res = !l || (l && r);
    }
    idx++;
    return res;
  default:
    return ((S >> (s[idx]-'a')) & 1);
  }
}

bool solve(const string &s){
  int eq = s.find('=');
  string l = s.substr(0,eq);
  string r = s.substr(eq+1);
  for(S = 0 ; S < (1<<11) ; S++){
    idx = -1;
    bool ll = parse(l);
    idx = -1;
    if(ll != parse(r)){
      return false;
    }
  }
  return true;
}

int main(){
  string s;
  while(cin >> s, s != "#"){
    cout << (solve(s) ? "YES" : "NO") << endl;
  }
  return 0;
}

Measured memory_bytes: 1220
#include <stdio.h>
int main(void){
    int x, i, n;
    scanf("%d", &x);
    i=1;
    
    while(i <= x){
        n=i;
        if(n%3 == 0){
            printf(" %d", i);
        }
        else{
            do{
                if(n%10 == 3){
                    printf(" %d", i);
                    break;
                }
                n /= 10;
            }while(n);
        }
        i++;
    }
    printf("\n");
    return 0;
}




Measured memory_bytes: 2112