akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <set>

using namespace std;

typedef long long ll;

template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

const vector<int> dx = {-1, 0, 1, 0};
const vector<int> dy = {0, -1, 0, 1};

ll to_id(const vector<vector<int>> &board) {
    ll acc = 0;
    for (int i = 0; i < 9; i++) {
        int row = i / 3;
        int col = i % 3;
        acc = acc * 10 + board[row][col];
    }
    return acc;
}

vector<vector<int>> to_board(ll id) {
    vector<vector<int>> board(3, vector<int>(3));
    for (int i = 2; i >= 0; i--) {
        for (int j = 2; j >= 0; j--) {
            board[i][j] = id % 10;
            id /= 10;
        }
    }
    return board;
}

// {row, col}
pair<int, int> find(const int v, const vector<vector<int>> &board) {
    int row;
    int col;
    for (int i = 0; i < 9; i++) {
        row = i / 3;
        col = i % 3;
        if (board[row][col] == v) break;
    }
    return {row, col};
}

void print_board(const vector<vector<int>> &board) {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            printf("%d ", board[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

set<ll> visited;

int main(void) {
    vector<vector<int>> start(3, vector<int>(3));
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> start[i][j];
        }
    }

    const vector<vector<int>> goal = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 0}
    };
    const auto goal_id = to_id(goal);

    // {id, dist}
    queue<pair<ll, int>> q;
    auto start_id = to_id(start);
    q.push({start_id, 0});
    visited.insert(start_id);

    if (start_id == goal_id) {
        cout << 0 << endl;
        return 0;
    }

    int ans = -1;
    while (!q.empty()) {
        const auto node = q.front();
        q.pop();
        const auto cur_board_id = node.first;
        const auto cur_board = to_board(cur_board_id);
        const auto cur_dist = node.second;
        const auto zero_pos = find(0, cur_board);
        // print_board(cur_board);

        for (int i = 0; i < 4; i++) {
            auto b = cur_board;
            const int next_row = zero_pos.first + dy[i];
            const int next_col = zero_pos.second + dx[i];
            if (next_row < 0 || next_row > 2 || next_col < 0 || next_col > 2) continue;

            swap(b[zero_pos.first][zero_pos.second], b[next_row][next_col]);
            auto id = to_id(b);
            auto dist = cur_dist + 1;
            if (visited.find(id) != visited.end()) continue;
            visited.insert(id);
            if (id == goal_id) {
                ans = dist;
                break;
            }
            q.push({id, dist});
        }
    }

    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 11700
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
bool bo[100];
#define ll long long 

int main()
{
	string s;
	cin>>s;
	ll q,w;
	for(int i=0;i<(int)s.size();i++)
	{
		if(s[i]=='A')
		{
			q=i;
			break;
		}
	}
	//cout<<q<<endl;
	for(int i=0;i<(int)s.size();i++)
	{
		if(s[i]=='Z')
		{
			w=i;
			//break;
		}
	}
	//cout<<w<<endl;
	cout<<w-q+1<<endl;
}


Measured memory_bytes: 640
N, M = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(N)]
PRICE = 0
NBOTTLE = 1

AB.sort() # price昇順でソート
bought = 0
paid = 0
for i in range(N):
    if bought >= M: break
    buy = min(M - bought, AB[i][NBOTTLE])
    bought += buy
    paid += buy * AB[i][PRICE]

print(paid)

Measured memory_bytes: 21612
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,c=0;
    string s;

    cin>>n;
  cin>>s;
      for(i=0;i<n/2;i++)
      {
          if(s[i]==s[(n/2)+i])
            c++;
      }
      if(n%2==1)
        cout<<"No"<<endl;
  else if(c==n/2)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;

   return 0;
}


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

#define mod 1000000007

const int N=100005;
int cache[N];
int h[N];
int n;

int dp(int n)
{
    if(n==0)
        return 0;
    if(n<0)
        return 1e8;
    if(cache[n]!=-1)
        return cache[n];
    else
    {
        cache[n]=min(abs(h[n]-h[n-2])+dp(n-2),abs(h[n]-h[n-1])+dp(n-1));
        return cache[n];
    }
}

signed main()
{

    memset(cache,-1,sizeof(cache));

    cin>>n;
    for(int i=0;i<n;i++)
        cin>>h[i];
    cout<<dp(n-1)<<endl;

    return 0;
}

Measured memory_bytes: 5760
/*
	Copyright: razouq (c)
	Author: Anass BENDARSI
	Date: 10/06/2017 12:37:59
	flamers will **** you
*/
#include<bits/stdc++.h>
//#include<flamers.h>
#define ull unsigned long long
using namespace std;
	string str;

void add(string c, int p){
	string s = "";
	for(int i = 0; i < str.size(); ++i){
		if(i == p) s += c;
		s += str[i];
	}
}

int main(){
	int n;
	cin>>n;
	cin>>str;
	string h;
	int k = 0, f = 0;
	for(int i = 0; i < str.size(); i++){
		
		if(str[i] == '(') k++;
		else k--;
		if(k < 0) {
			f -= k;
			k = 0;
		}
		
	}
	for(int i = 0; i < f; i++){
		str = "(" + str;
	}
	 k = 0;
	for(int i = 0; i < str.size(); i++){
		if(str[i] == '(') k++;
		else k--;
	}
	for(int i = 0; i < k; i++){
		str += ')';
	}
	cout<<str<<endl;
	return 0;
}


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

int main(){
    double a,b,c,d,e,f;
    cin >> a >> b >> c >> d >> e >> f;
    vector<double> w,s;
    for(int i = 0; 100 * a * i <= f; i++ ){
        for(int j = 0; 100 * b * j <= f; j++ ){
            w.push_back((100 * a * i) + (100 * b * j));
        }    
    }
    for(int i = 0; c * i <= f; i++ ){
        for(int j = 0; d * j <= f; j++ ){
            s.push_back((c * i) + (d * j));
        }    
    }

    double noudo = (100 * e / (100 + e));
    double noudo2;
    int anss = 0,ansmass = 0;
    double ans = 0.00000;

    for(int i = 0; i < w.size(); i++){
        for(int j = 0; j < s.size(); j++){
            if(w[i] + s[j] == 0) ans = 0;
            else{
                noudo2 = 100 * s[j] / (w[i] + s[j]);
                if(w[i] + s[j] <= f and noudo >= noudo2){
                    if(ans <= noudo2){
                        ans = noudo2;
                        ansmass = w[i] + s[j];
                        anss = s[j];
                    }
                }
            }
        }
    }
    cout << ansmass << " " << anss << endl;
}

Measured memory_bytes: 5364
#include <bits/stdc++.h>
#include <iomanip>
#include <math.h>
#define rep(i,x) for(ll i = 0;i<x;i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using namespace std;
using dou = double;
const ll INF = 1LL << 60;
const ll mod = 1000000007;
typedef pair<ll,ll> P;
using graph = vector<vector<ll>>;
template<class T> inline bool chmax(T& a, T b){if(a < b){a = b; return true;}return false;}
template<class T> inline bool chmin(T& a, T b){if(a > b){a = b; return true;}return false;}
ll gcd(ll a,ll b){
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
bool isp(ll n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}
//printf("%.10f\n", N);
/*
ll fibo(ll n){
    if(memo[n] != 0)return memo[n];
    if(n <= 1)return n;
    else return memo[n] = fibo(n - 1)+ fibo(n - 2);
}*/
/*  vector<ll> vec = {1,2,5,6,8,9,10};
    cout << binary_search(all(vec),5) << endl; -> true*/
/*
    vector<ll> vec = {1,2,5,6,8,9,10};
    auto n = upper_bound(all(vec),4);
    cout << *n << endl; -> 5*/
/*
    cout << fixed << setprecision(15);
    */
int main(){
    vector<vector<ll>> card(3,vector<ll>(3));
    ll N;
    rep(i,3)
    rep(j,3)cin >> card[i][j];
    cin >> N;
    bool ans = false;
    vector<ll> num(N);
    rep(i,N)cin >> num[i];
    vector<vector<bool>> ok(3,vector<bool>(3,false));
    rep(i,N){
        rep(j,3){
            rep(k,3){
                if(card[j][k] == num[i]){
                    ok[j][k] = true;
                }
            }
        }
    }
    rep(i,3){
        if(ok[i][0] && ok[i][1] && ok[i][2])ans = true;
        if(ok[0][i] && ok[1][i] && ok[2][i])ans = true;
    }
    if(ok[0][0] && ok[1][1] && ok[2][2])ans = true;
    if(ok[2][0] && ok[1][1] && ok[0][2])ans = true;
    if(ans)cout << "Yes" << endl;
    else cout << "No" << endl;
    /*rep(i,3)
    rep(j,3)cout << ok[i][j] << " ";
    rep(i,3)
    rep(j,3)cout << card[i][j] << " ";*/
}

Measured memory_bytes: 256
macro_rules! get {
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
            get!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
            get!($($t),*)
        ).collect::<Vec<_>>()
    };
}

use std::cmp;

fn main() {
    let _n = get!(usize);
    let k = get!(i32);
    let xx = get!(String).split_whitespace().map(|i| i.parse::<i32>().unwrap()).collect::<Vec<_>>();
    let mut r = 0;
    for x in xx.into_iter() {
        r += cmp::min(x, (k - x).abs()) * 2;
    }
    println!("{}", r);
}

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

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) begin(r),end(r)
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)
#define vvl(v,w,h,init) vector<vector<ll>> v(w,vector<ll>(h,init))
#define mp(a,b) make_pair(a,b)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using pii = pair<int,int> ;
using pll = pair<ll,ll> ;

const int mod = 1000000007;
constexpr ll inf = ((1<<30)-1)*2+1 ;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0,1,-1,1,-1};
const int dx[] = {0,-1,0,1,1,-1,-1,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n,cnt = 0,s = 0;
  cin >> n;
  vector<ll> v(n);
  rep(i,n){
    cin >> v[i];
  }
  ll p = 1;
  rep(i,n){
    if(i == 0){
      cnt += v[i] - 1;
      p = 1;
    }
    else if(p+1 == v[i]){
      ++p; 
    }
    else if(p + 1 < v[i]){
      cnt += (v[i] - 1) / (p+1);
    }
  }
  cout << cnt << endl;
  return 0;
}



Measured memory_bytes: 1152
n,x=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
ans=1
curr=0
ind=0
while(curr<=x):
    if(ind>=n):
        break
    curr+=a[ind]
    ind+=1
    if(curr>x):
        break
    ans+=1
print(ans)


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

const int N = 1e5 + 10;

int n, x, ans[N << 1];

int main() {
#ifdef LOCAL
    freopen("C:\\Users\\Administrator\\Desktop\\in.txt", "r", stdin);
    freopen("C:\\Users\\Administrator\\Desktop\\out.txt", "w", stdout);
#endif
    scanf("%d%d", &n, &x);
    if (x == 1 || x == n * 2 - 1) {
        printf("No\n");
        return 0;
    }
    printf("Yes\n");
    x--;
    for (int i = 0; i < n * 2 - 1; i++) {
        ans[(n + i - 1) % (n * 2 - 1)] = x + 1;
        x++;
        x %= (n * 2 - 1);
    }
    for (int i = 0; i < n * 2 - 1; i++) printf("%d\n", ans[i]);
    return 0;
}


Measured memory_bytes: 2304
import sys
from fractions import gcd
input = sys.stdin.readline

class DisjointSparseTable:
    def __init__(self, a):
        self.level = (len(a) - 1).bit_length()
        self.size = 2**self.level
        self.table = [[0] * self.size for _ in range(self.level)]
        # Set bottom first
        for i, item in enumerate(a): 
            self.table[-1][i] = item
        self.build()

    def build(self):
        for lv in range(1, self.level):
            step = 2**lv
            level = self.level - 1 - lv
            for mid in range(step, self.size, step*2):
                # Calc forward
                val = 0
                for i in range(step):
                    val = gcd(self.table[-1][mid + i], val)
                    self.table[level][mid + i] = val
                # Calc backward
                val = 0
                for i in range(step):
                    val = gcd(self.table[-1][mid - 1 - i], val)
                    self.table[level][mid - 1 - i] = val
    
    # Returns f[l:r)
    def query(self, l, r):
        if l == r:
            return 0
        elif l == r - 1:
            return self.table[-1][l]
        level = self.level - (l ^ r-1).bit_length()
        return gcd(self.table[level][l], self.table[level][r-1])

if __name__ == "__main__":
    n = int(input())
    a = [int(item) for item in input().split()]
    DST = DisjointSparseTable(a)
    ans = 0
    for i in range(0, n):
        ans = max(ans, gcd(DST.query(0, i), DST.query(i+1, n)))
    print(ans)

Measured memory_bytes: 101216
#include <bits/stdc++.h>
#define MAX_N 200001
#define mod 1000000007
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define FOR(i, a, b) for(ll i=a; i<b; i++)
#define REP(i, n) for(ll i=0; i<n; i++)
#define REV(i, n) for(ll i=n-1; i>=0; i--)
#define ALL(v) v.begin(), v.end()
#define pb push_back
const ll INF = 9e18;
ll n, m;

signed main(){
    cin >> n >> m;
    REP(i, (m+1)/2){
        cout << i + 1 << " " << ((m % 2 == 0) ? (m - i) : (m - i + 1)) << endl;
    }

    REP(i, m/2){
        cout << ((m % 2 == 0) ? (m + i + 1) : (m + i + 2)) << " " << ((m % 2 == 0) ? (2 * m - i + 1) : (2 * m - i + 1)) << endl;
    }

    return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  loop(i,0,n)
#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()
#define vi vector<int>
#define vl vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>

int main(){
    string s,t;
    cin>>s>>t;
    int a,b;
    cin>>a>>b;
    string u;
    cin>>u;

    if(u==s){
        cout<<a-1<<" "<<b<<endl;
    }
    else{
        cout<<a<<" "<<b-1<<endl;
    }
    
}

Measured memory_bytes: 256
#include <stdio.h>
#define MAX 8
#define FREE -1
#define NOTFREE 1

int mat[MAX][MAX],row[MAX],col[MAX],right[2*MAX-1],left[2*MAX-1];

void print()
{
  int i,j;
  for(i=0;i<MAX;i++){
    for(j=0;j<MAX;j++){
      if(mat[i][j]){
        if(row[i]!=j) return;
      }
    }
  }
  for(i=0;i<MAX;i++){
    for(j=0;j<MAX;j++){
      if(row[i]==j) printf("Q");
      else printf(".");
    }
    printf("\n");
  }
}

void queen(int i)
{
  int j;
  if(i==MAX){
    print();
    return;
  }
  for(j=0;j<MAX;j++){
    if(col[j]==NOTFREE ||
       right[i+j]==NOTFREE ||
       left[i-j+MAX-1]==NOTFREE) continue;

    row[i]=j;
    col[j]=NOTFREE;
    right[i+j]=NOTFREE;
    left[i-j+MAX-1]=NOTFREE;

    queen(i+1);
    row[i]=FREE;
    col[j]=FREE;
    right[i+j]=FREE;
    left[i-j+MAX-1]=FREE;
  }
}

int main()
{
  int n,i,j,r,c;

  for(i=0;i<MAX;i++){
    row[i]=FREE;
    col[i]=FREE;
  }
  for(i=0;i<2*MAX-1;i++){
    right[i]=FREE;
    left[i]=FREE;
  }

  for(i=0;i<MAX;i++){
    for(j=0;j<MAX;j++){
      mat[i][j]=0;
    }
  }

  scanf("%d",&n);
  for(i=0;i<n;i++) {
    scanf("%d%d",&r,&c);
    mat[r][c]=1;
  }
  queen(0);

  return 0;

}



Measured memory_bytes: 2108
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF (1e9+1)
//#define INF (1LL<<59)






#define MAX_V 100
struct edge { int to, cap, cost,rev; };

int V; // ????????°
vector<edge> G[MAX_V];
vector<int> h(MAX_V);	//??????????????£???
int dist[MAX_V];// ???????????¢
int prevv[MAX_V], preve[MAX_V];// ??´??????????????¨???

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


int shortest_path(int s,vector<int> &d){
	int v = d.size();
	rep(i,d.size())d[i]=INF;
	d[s]=0;
	rep(loop,v){
		bool update = false;
		rep(i,MAX_V){
			for(auto e:G[i]){
				if(d[i]!=INF && d[e.to] > d[i]+e.cost){
					d[e.to] = d[i]+e.cost;
					update = true;
				}
			}
		}
		if(!update)break;
		if(loop==v-1)return true;	//negative_cycle
	}
	return false;
}


// s??????t????????????f???????°??????¨???????±???????
// ??????????????´??????-1?????????
int min_cost_flow(int s, int t, int f) {
	int res = 0;
	rep(i,h.size())h[i]=0;
	bool hoge=false;
	while (f > 0) {
		// ?????????????????????????????¨??????h?????´??°??????
		if(!f){
			shortest_path(s, h);
			f=true;
		}
		else{
			priority_queue<pii, vector<pii>, greater<pii> > que; fill(dist, dist + V, INF);
			dist[s] = 0;
			que.push(pii(0, s));
			while (!que.empty()) {
				pii p = que.top(); que.pop();
				int v = p.second;
				if (dist[v] < p.first) continue;
				for (int i = 0; i < G[v].size(); i++) {
					edge &e = G[v][i];
					if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
						dist[e.to] = dist[v] + e.cost + h[v] - h[e.to]; prevv[e.to] = v;
						preve[e.to] = i;
						que.push(pii(dist[e.to], e.to));
					}
				}
			}
		}
		if (dist[t] == INF) return -1;	//????????\???????????????
		
		for (int v = 0; v < V; v++) h[v] += dist[v];
		
		// s-t????????????????????£??????????????????
		int d = f;
		for (int v = t; v != s; v = prevv[v]) {
			d = min(d, G[prevv[v]][preve[v]].cap);
		}
		f -= d;
		res += d * h[t];
		for (int v = t; v != s; v = prevv[v]) {
			edge &e = G[prevv[v]][preve[v]]; e.cap -= d;
			G[v][e.rev].cap += d;
		}
	}
	return res;
}

int main(){
	int e,f;
	cin>>V>>e>>f;
	rep(i,e){
		int u,v,c,d;
		cin>>u>>v>>c>>d;
		add_edge(u, v, c, d);
	}
	cout<<min_cost_flow(0, V-1, f)<<endl;
}

Measured memory_bytes: 3172
#include <iostream>
#include <map>

std::map<std::pair<int, int>, int> mapa;

int findfirst(int x) {
	int tmp = 1'000'000;
	while (x / tmp == 0) tmp /= 10;

	return x/tmp;
}

int main() {
	int n;
	std::cin >> n;

	long long int ans = 0;
	long long int same = 0;
	for (int i = 1; i <= n; ++i) {

		int first = findfirst(i);
		int last = i % 10;
		std::pair<int, int> pr = std::make_pair(first, last);
		std::pair<int, int> reversepr = std::make_pair(last, first);

		if (first == last) {
			++same;
		}

		ans += mapa[reversepr];
		++mapa[pr];
	}

	std::cout << 2*ans + same;
}

Measured memory_bytes: 3560
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Program
{
    static void Main(string[] args)
    {
        new Program().Solve();
    }

    void Solve()
    {
        Scanner cin = new Scanner();
        int n = cin.NextInt();
        int m = cin.NextInt();
        int[] a = new int[m];
        for (int i = 0; i < m; i++)
        {
            a[i] = cin.NextInt();
        }
        int len = n + 1;
        long[] dp = Enumerable.Repeat((long)0, len).ToArray();
        dp[0] = 1;

        foreach (var item in a)
        {
            dp[item] = -1;
        }
        if (dp[1] >= 0)
        {
            dp[1] = 1;
        }

        for (int i = 2; i < len; i++)
        {
            if (dp[i] == -1)
            {
                continue;
            }
            if (dp[i-1] >= 0 && dp[i-2] >= 0)
            {
                dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
            }
            else if (dp[i-1] >= 0)
            {
                dp[i] = dp[i - 1];
            }
            else if (dp[i-2] >= 0)
            {
                dp[i] = dp[i - 2];
            }
            else
            {
                break;
            }
        }
        Console.WriteLine(dp[n]);
    }
}


class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string Next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return Next();
        i = 0;
        return s[i++];
    }

    public int NextInt()
    {
        return int.Parse(Next());
    }

    public char[] ArrayChar()
    {
        return Next().ToCharArray();
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = NextInt() + add;
        }
        return Array;
    }

    public long NextLong()
    {
        return long.Parse(Next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = NextLong() + add;
        }
        return Array;
    }

    public double NextDouble()
    {
        return double.Parse(Next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = NextDouble() + add;
        }
        return Array;
    }
}

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

typedef vector<pair<int, int>> vii;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
int n, s;
ll memo[101][(int) (1e5) + 2];
int w[101];
int v[101];
ll dp(int idx, int remw) {
	if (remw < 0)
		return -(1e9);
	if (idx == n)
		return 0;
	if (memo[idx][remw] != -1)
		return memo[idx][remw];
	ll take = v[idx] + dp(idx + 1, remw - w[idx]);
	ll leave = dp(idx + 1, remw);
	return memo[idx][remw] = max(take, leave);
}
int main() {
	ios::sync_with_stdio(false), cin.tie(0);
//	freopen("sort.in", "r", stdin);
//	freopen("sort.txt", "w", stdout);
	cin >> n >> s;
	for (int i = 0; i < n; i++)
		cin >> w[i] >> v[i];
	for (int i = 0; i < n; i++)
		for (int j = 0; j <= s; j++)
			memo[i][j] = -1;
	cout << dp(0, s);
	return 0;
}



Measured memory_bytes: 81760
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define all(a) a.begin(), a.end()
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; }
using namespace std;

template<const long long mod = 1000000007>
struct mint{ //modint
    long long x;
    mint(long long x = 0): x((x %= mod) < 0 ? x + mod : x) {}
    friend istream& operator >> (istream &s, mint& m){ return s >> m.x; }
    friend ostream& operator << (ostream &s, mint m){ return s << m.x; }
    inline mint& operator += (mint a){ if((x += a.x) >= mod)x -= mod; return *this; }
    inline mint& operator -= (mint a){ if((x += mod - a.x) >= mod)x -= mod; return *this; }
    inline mint& operator *= (mint a){ (x *= a.x) %= mod; return *this; }
    inline mint& operator /= (mint a){ return (*this) *= a.inv(); }
    inline mint operator + (mint a){ mint res(*this); return res += a; }
    inline mint operator - (mint a){ mint res(*this); return res -= a; }
    inline mint operator * (mint a){ mint res(*this); return res *= a; }
    inline mint operator / (mint a){ mint res(*this); return res /= a; }
    inline void takemod(){ x = ((x % mod) + mod) % mod; }
    inline mint inv(){
        long long a = x, b = mod, u = 1, v = 0, t;
        while(b){
            t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        return mint(u);
    }
    inline mint pow(long long p){
        mint res(1), tmp(x);
        for(; p; p >>= 1){ if(p & 1)res *= tmp; tmp *= tmp; }
        return res;
    }
};

mint<> dp[201][100001];

int main(){

    int N, X;
    cin >> N >> X;

    vector<int> S(N);
    rep(i, N)cin >> S[i];
    sort(all(S));

    rep(j, X + 1)dp[0][j] = mint<>(j);
    rep(i, N)rep(j, X + 1){
        dp[i + 1][j] = mint<>(i) * dp[i][j] + dp[i][j % S[i]];
    }

    cout << dp[N][X] << endl;
    return 0;

}

Measured memory_bytes: 157312
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

int main() {
    int D, G;
    cin >> D >> G;
    if (D * 100 >= G) {
        cout << 1 << endl;
        return 0;
    }
    vector<int> P(D), C(D);
    rep(i, D) {
        cin >> P.at(i) >> C.at(i);
    }
    int res = accumulate(P.begin(), P.end(), 0);
    for (int mask = 0; mask < 1<<D; mask++) {
        int restmax = 0, sum = 0, total = 0;
        for (int i = 0; i < D; i++) {
            if (mask & 1 << i) {
              sum += 100 * (i + 1) * P[i] + C[i];
              total += P[i];
            } else {
              restmax = i;
            }
        }
        if (sum >= G) {
            res = min(res, total);
            continue;
        }
        if (G > sum && G - sum > (P[restmax] - 1) * 100 * (restmax+1)) continue;
        total += (G - sum) / ((restmax + 1) * 100);
        res = min(res, total);
    }
    cout << res << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long dp[101][100005];
int v[101],w[101];
int W,n;
int main()
{
    cin>>n>>W;
    for(int i=1;i<=n;i++)
    {
      cin>>w[i]>>v[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=W;j++)
        {
            dp[i][j]=dp[i-1][j];
            if(j>=w[i])
            dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
        }
    }
    cout<<dp[n][W]<<endl;
    return 0;
}


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

struct Node{
	int key;
	struct Node *next, *prev;
};

struct Node *nil;

struct Node* listSearch(int key){
	struct Node *cur = nil->next;
	while(cur != nil && cur->key!=key){
		cur=cur->next;
	}
	return cur;
}

void init(){
	nil=(struct Node *)malloc(sizeof(struct Node));
	nil->next=nil;
	nil->prev=nil;
}

void printList(){
	struct Node *cur= nil->next;
	int isf=0;
	while(1){
		if(cur==nil){break;}
		if(isf++ >0){printf(" ");}
		printf("%d",cur->key);
		cur=cur->next;
	}
	printf("\n");
}

void deleteNode(struct Node *t){
	if(t==nil){return;}
	t->prev->next=t->next;
	t->next->prev=t->prev;
	free(t);
}

void deleteFirst(){
	deleteNode(nil->next);
}

void deleteLast(){
	deleteNode(nil->prev);
}

void deleteKey(int key){
	deleteNode(listSearch(key));
}

void insert(int key){
	struct Node *x=(struct Node *)malloc(sizeof(struct Node));
	x->key=key;
	x->next=nil->next;
	nil->next->prev=x;
	nil->next=x;
	x->prev=nil;
}

int main(void){
	int key,n,i;
	int size=0;
	char com[20];
	int np=0 , nd=0;
	scanf("%d",&n);
	init();
	for(i=0; i<n; i++){
		scanf("%s%d",com,&key);
		if(com[0]=='i'){insert(key); np++; size++;}
		else if(com[0]=='d'){
		if(strlen(com)>6){
			if(com[6]=='F'){deleteFirst();}
			else if(com[6]=='L'){deleteLast();}
		}else{
			deleteKey(key); nd++;
		}
		size--;
	}
}

printList();

return 0;
}


Measured memory_bytes: 32968
// DP F

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

typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const int INF = 1e9;
const long long INFL = 1LL<<60;

void dump(const vector<pair<int, int>>& a)
{
  for (auto v : a) {
    cerr << v.first << " " << v.second << endl;
  }
}

////////////////////////////////////////////////////

static const int MAX = 100;

int n;
ll d[MAX][MAX];

void floyd()
{
  rep(k, n) {
    rep(i, n) {
      if (d[i][k] == INFL) {
        continue;
      }
      rep(j, n) {
        if (d[k][j] == INFL) {
          continue;
        }
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }
}

int main()
{
  int e, u, v, c;
  cin >> n >> e;

  rep(i, n) {
    rep(j, n) {
      d[i][j] = ((i == j) ? 0 : INFL);
    }
  }

  rep(i, e) {
    cin >> u >> v >> c;
    d[u][v] = c;
  }

  floyd();

  rep(i, n) {
    if (d[i][i] < 0) {
      cout << "NEGATIVE CYCLE" << endl;
      return 0;
    }
  }

  rep(i, n) {
    rep(j, n) {
      if (j) {
        cout << " ";
      }
      if (d[i][j] == INFL) {
        cout << "INF";
      } else {
        cout << d[i][j];
      }
    }
    cout << endl;
  }

  return 0;
}



Measured memory_bytes: 3176
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll n,i,j,k,l,a,b,c,d,s;
    cin>>n;
    vector<ll>u,v;
    v.push_back(0);
    for(i=0;i<n;i++)
    {
        cin>>k;
        v.push_back(k);
    }
    v.push_back(0);
    s=0;
    for(i=1;i<=n+1;i++)
    {
        s+=abs(v[i]-v[i-1]);
    }

    for(i=1;i<n+1;i++)
    {
        c=s;
        c-=abs(v[i]-v[i-1]);
        c-=abs(v[i+1]-v[i]);
        c+=abs(v[i+1]-v[i-1]);
        cout<<c<<endl;
    }
    return 0;
}


Measured memory_bytes: 2164
#include <iostream>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <functional>
using namespace std;

#define All(v) (v).begin(),(v).end()
int dy[8] = {-1,0,1,0,-1,1,1,-1};
int dx[8] = {0,1,0,-1,1,1,-1,-1};
const long long mod = 1000000007;

signed main(){
    long long n;
    cin>>n;
    vector<long long> a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    long long res=0;
    for(int i=0;i<60;i++){
        long long b=0,d=0;
        for(int j=0;j<n;j++){
            if(a[j]&(1ll<<i)){
                b++;
            }else{
                d++;
            }
        }
        res+=(1ll<<i)%mod*b%mod*d%mod;
    }
    cout<<res%mod<<endl;
}


Measured memory_bytes: 2560
import math
import numpy as np


#横並び
#a, b, c, x = map(int, [input() for i in range(4)])
#z = list(map(int, input().split()))
#n, a, b = map(int, input().split())

#print(len(z))
#for i in z:
#    print(i)

#a = sorted(a,reverse = True)
#print(sum(a[::2]) - sum(a[1::2]))
#z = map(int, [input() for i in range(int(n))])
#data_list = [ list(map(int,input().split(" "))) for i in range(3)]


n = int(input())
a = list(map(int,input().split()))
k = 0
for i in a:
    k += 1/i


print(1/k)


Measured memory_bytes: 14420
fun main(args: Array<String>) {
    val n = readInputLine().toInt()
    
    val aList = readInputLine().split(" ").map { it.toInt() }

    val map = mutableMapOf<Int, Int>()
    
    for (i in 0 until n) {
        val noOpNum = map.get(aList[i]) ?: 0
        val plusNum = map.get(aList[i] + 1) ?: 0
        val minusNum = map.get(aList[i] - 1) ?: 0
        
        map.put(aList[i], noOpNum + 1)
        map.put(aList[i] + 1, plusNum + 1)
        map.put(aList[i] - 1, minusNum + 1)
    }
    
    println(map.maxBy { it.value }!!.value)
}
 
fun readInputLine(): String {
    return readLine()!!
}


Measured memory_bytes: 59288
N, X, T = map(int, input().split())
count = 1
check = X
if X > 1:
    while True:
        value = int(N / X)
        re = N % X
        if re == 0:
            count = value
            TotalTime = T * count
            break
        else:
            count += value
            TotalTime = T * count
            break
else:
    TotalTime = T * N
print(TotalTime)

Measured memory_bytes: 9176
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define p push
#define ll long long
#define fi first
#define se second	
#define pii pair< int , int >
#define pll pair< long , long >
#define pi acos(-1.0)
#define _FAST ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define MOD 10e9+7
#define line puts("")


using namespace std;

int ans,n,m,a[205][205],cost[11][11];

int main(){
	cin>>n>>m;
	for(int i=0;i<10;i++)
		for(int j=0;j<10;j++) cin>>cost[i][j];
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++) cin>>a[i][j];
	for(int k=0;k<10;k++){
		for(int i=0;i<10;i++){
			for(int j=0;j<10;j++)
				if(cost[i][k] + cost[k][j] < cost[i][j]){
					cost[i][j] = cost[i][k] + cost[k][j];
				}
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(a[i][j] != -1){
				ans += cost[a[i][j]][1];
			}
		}
	}
	cout<<ans<<endl;
}

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

int main() {
  int n;
  cin >> n;
  priority_queue<double, vector<double>, greater<double>> q;
  rep(i,0,n) {
    double v;
    cin >> v;
    q.push(v);
  }
  rep(i,0,n-1) {
    double v1 = q.top(); q.pop();
    double v2 = q.top(); q.pop();
    q.push((v1+v2)/2);
  }
  double ans = q.top();
  printf("%.10lf\n", ans);
  return 0;
}


Measured memory_bytes: 3604
#include<iostream>
#include<algorithm>

using namespace std;

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

	if (a > b){
		swap(a, b);
	}
	if (b > c){
		swap(b, c);
	}
	if (a > b){
		swap(a, b);
	}
	cout << a << " " << b << " " << c << endl;
	return 0;
}

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

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using pint = pair<int, int>;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const int MOD = 1000000009;
const long long INF = 1LL << 60;

int main() {
    int A, B, C, X, Y;
    cin >> A >> B >> C >> X >> Y;
    ll AB_SUM = A*X+B*Y;
    ll C_SUM = C*max(X, Y)*2;
    bool flg = false;
    if (X > Y) flg = true;
    ll MIX_SUM = C*min(X, Y)*2 + abs(X-Y)*(flg ? A : B);
    cout << min(min(AB_SUM, C_SUM), MIX_SUM) << endl;
    return 0;
}

Measured memory_bytes: 3640
package main

import (
	"fmt"
)

func main() {
	var n,y,total int
	fmt.Scan(&n,&y)
	
	for a := 0; a <= n; a++ {
		for b := 0; b <= n; b++ {
			c := n - (a + b)
			total =  10000 * a + 5000 * b + 1000 * c
			if a + b + c == n && total == y && c >= 0{
				fmt.Printf("%d %d %d",a,b,c)
				return
			}
		}
	}
	fmt.Println("-1 -1 -1")
}


Measured memory_bytes: 512
#include <iostream>
using namespace std;
string a;
int c[130];
int main() {
	cin>>a;
	for(int i=0; a[i]; i++) {
		c[a[i]]++;
		if(c[a[i]]==2) {cout<<"no"; return 0;}
	}
	cout<<"yes";
	return 0;
}

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

int main(void)
{
	int grid[3][3], a[3], b[3];
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			scanf("%d", &grid[i][j]);
		}
	}

	a[0] = 0;
	b[0] = grid[0][0] - a[0];
	a[1] = grid[1][0] - b[0];
	b[1] = grid[0][1] - a[0];
	a[2] = grid[2][0] - b[0];
	b[2] = grid[0][2] - a[0];
	
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (grid[i][j] != (a[i] + b[j])) {
				printf("No\n");
				return 0;
			}
		}
	}

	printf("Yes\n");
	return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

ll dp[20000][256];

int round_255(int x) {
    if(x < 0) return 0;
    else if(x <= 255) return x;
    else return 255;
}

int main(void)
{   
    while(1) {
        int n, m;
        cin >> n >> m;
        if(n == 0 and m == 0) break;
        vector<int> x(n), c(m);
        rep(i, m) cin >> c[i];
        rep(i, n) cin >> x[i];

        rep(i, n)rep(j, 256) dp[i][j] = 1L<<60;

        rep(i, m) {
            int y = round_255(128 + c[i]);
            dp[0][y] = (x[0] - y)*(x[0] - y);
        }
    
        rep(i, n) {
            if(i == 0) continue;
            rep(j, 256) {
                rep(k, m) {
                    int y = round_255(j + c[k]);
                    dp[i][y] = min(dp[i][y], dp[i-1][j] + (x[i] - y)*(x[i] - y));
                }
            }
        }

        ll ans = 1L<<60;
        rep(i, 256) {
            ans = min(ans, dp[n-1][i]);
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 43128
l=[[True for i in range(13)] for i in range(4)]
d=['S','H','C','D']
n=int(input())
for i in range(n):
    a,b=input().split()
    a=d.index(a)
    l[a][int(b)-1]=False
for i in range(4):
    for j in range(13):
        if l[i][j]:
            print(d[i],j+1)


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

int main(){
  	int N,M;
  	cin >> N >> M;
  	vector<int> count(M);
  	for(int i=0; i<N; i++){
      	int K;
      	cin >> K;
    	for(int j=0; j<K; j++){
          	int m;
          	cin >> m;
        	count[m-1]++;
        }
    }
  	int ans=0;
  	for(int i=0; i<M; i++){
      	if(count[i] == N) ans++;
    }
  	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import sys
import math
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N = math.factorial(int(input()))
    i = 2
    ans = 1
    while i * i < N:
        cnt = 1
        while N % i == 0:
            cnt += 1
            N //= i
        ans *= cnt
        i += 1
    if N != 1:
        ans *= 2

    print(int(ans % (10 ** 9 + 7)))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
N, M = map(int, input().split())
a_list = [int(input()) for _ in range(M)]

mod = 10 ** 9 + 7

dp = [0] * (N + 100)
dp[0] = 1
not_use = [False] * (N + 100)
for a in a_list:
    not_use[a] = True

for i in range(N+1):
    not_u = not_use[i]
    if not_u:
        continue
    else:
        dp[i + 1] += dp[i]
        dp[i + 1] %= mod
        dp[i + 2] += dp[i]
        dp[i + 2] %= mod

print(dp[N] % mod)


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

using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n; i>-1; --i)
#define ALL(a) (a).begin(),(a).end()
#define FILL(a,n,x); REP(i,(n)){ (a)[i]=(x); }
#define CINA(a,n); REP(i,(n)){ cin >> (a)[i]; }
#define FILL2(a,n,m,x); REP(i,(n)){ REP(j,(m)){(a)[i][j]=(x);} }
#define CINA2(a,n,m); REP(i,(n)){ REP(j,(m)){cin >> (a)[i][j];} }
#define Liny "Yes\n"
#define Linn "No\n"
#define LINY "YES\n"
#define LINN "NO\n"

//cout << setfill('0') << right << setw(4) << 12; // "0012"
int keta(ll x){ if(x<10){return 1;} else{return keta(x/10) + 1;}}
int keta_wa(ll x){ if(x<10){return x;} else{return keta_wa(x/10) + x%10;} }
int ctoi(char c){ return ( (c>='0' && c<='9')? c - '0': 0 );}
int __stoi(string s){ return atoi(s.c_str()); }
ll sum(ll a[],ll N){ return accumulate(a,a+N,0LL);}
ll gcd(ll a,ll b){if(a<b)swap(a,b); return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){if(a<b){swap(a,b);} return a/gcd(a,b)*b;}
template<class T> void chmax(T& a, T b){ if(a<b){a=b;} }
template<class T> void chmin(T& a, T b){ if(a>b){a=b;} }
template<class T> bool isIn(T a,vector<T> v){ for(T x:v){ if(a==x){return true;}} return false;}
string strReplace(string s,string target, string replacement){
    if (!target.empty()) {
      std::string::size_type pos = 0;
      while ((pos = s.find(target, pos)) != std::string::npos) {
        s.replace(pos, target.length(), replacement);
        pos += replacement.length();
      }
    }
    return s;
}
const ll MOD = 1e9+7;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair

bool DEBUG = 0;

template<class T> void dprint(T s){
  if(DEBUG){ cout << s << "\n"; }
}

int main(int argc, char *argv[]){
  if(argc>1 && argv[1][0]=='D'){ DEBUG = 1;}

  string t; cin>>t;
  int N = t.size();
  char s[N+1];
  REP(i,N){
    s[i+1] = t[i];
  }
  int ans1 = -1;
  int ans2 = -1;
  for(int i=1;i<=N;++i){
    if(i+1<=N && s[i]==s[i+1]){
      ans1 = i;
      ans2 = i+1;
      break;
    }
    if(i+2<=N && s[i]==s[i+2]){
      ans1 = i;
      ans2 = i+2;
      break;
    }
  }
  printf("%d %d\n",ans1,ans2);
}

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

using namespace std;

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

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

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

	string s;
	cin >> s;
	s.push_back('1');
	vector<int>box;
	int cnt = 0;
	for (auto i : s) {
		if (i == '1') {
			if (cnt % 2 == 0)box.push_back(min(2, cnt));
			cnt = 0;
		}
		else {
			cnt++;
		}
	}
	vector<vector<vector<long long int>>>dp(2, vector<vector<long long int>>(3, vector<long long int>(3)));
	dp[0][0][0] = 1;
	for (auto i : s) {
		vector<vector<vector<long long int>>>ndp(2, vector<vector<long long int>>(3, vector<long long int>(3)));
		if (i != '0') {
			for (int j = 0; j < 2; j++) {
				for (int k = 0; k < 3; k++) {
					for (int l = 0; l < 3; l++) {
						if (l == 1) {
							ndp[j][k][0] += dp[j][k][l];
							ndp[j][k][0] %= MOD;
							continue;
						}
						int nxj = j + 1;
						nxj &= 1;
						int nxk = k;
						int nxl = 0;
						if (j == 0 && l == 0 && nxk == 0)nxk = 1;
						if (j == 1 && l == 0 && nxk == 1)nxk = 2;
						ndp[nxj][nxk][nxl] += dp[j][k][l];
						ndp[nxj][nxk][nxl] %= MOD;
					}
				}
			}
		}
		if (i != '1') {
			for (int j = 0; j < 2; j++) {
				for (int k = 0; k < 3; k++) {
					for (int l = 0; l < 3; l++) {
						int nxl = l + 1;
						if (nxl == 3)nxl = 1;
						ndp[j][k][nxl] += dp[j][k][l];
						ndp[j][k][nxl] %= MOD;
					}
				}
			}
		}
		dp = ndp;
	}
	long long int ans = 0;
	for (int i = 0; i < 2; i++) {
		ans += dp[i][2][0];
		ans %= MOD;
	}
	cout << ans << endl;
}

Measured memory_bytes: 916
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int,null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define ordered_set_pair tree<pair<int,int>,null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update> 
#define ordered_set_mutiset tree<int,null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
typedef long long int ll;
typedef long double ld;
typedef unsigned long long int ull;
typedef pair<int,int> pi; 
#define PI 3.1415926535897932384
#define FOR(i,vv,n) for(ll i=vv;i<n;i++)
#define FORR(i,n,vv) for(ll i=n-1;i>=vv;i--)
#define ve vector 
#define maxind(v) (max_element(v.begin(),v.end())-v.begin())
#define minind(v) (min_element(v.begin(),v.end())-v.begin())
#define maxe(v) *max_element(v.begin(),v.end())
#define mine(v) *min_element(v.begin(),v.end())
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define eb emplace_back
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mp make_pair
#define M 1000000007ll
#define INF 1000000000000000000ll
#define PRECISE cout.precision(18);
#define all(v) v.begin(),v.end()
#define BS(v,n) binary_search(all(v),n)
#define srt(v) sort(v.begin(),v.end())
#define rsrt(v) sort(all(v),greater <ll>())
#define uni(v) v.resize(unique(all(v))-v.begin())
#define F first
#define S second
#define GET(i,p) get<p>(i)

const ll maxn=1000000+5;
const ll maxm=2*100000+5;
ll n=0;
ll tr[maxn][26];
ll m=1;
ve <ll> en(maxn);
ve <ll> z[maxn];
ve <string> v(maxm);
ve <ve <ve <ll> > > c(maxm);
void add1(string s,ll ind){
	ll u=0;
for(auto i:s){
	z[u].pb(ind);
if(tr[u][i-'a']==0)
	tr[u][i-'a']=m++;
u=tr[u][i-'a'];
}
en[u]++;
}
ll ans=0;

void dfs(ll u,ll f,ll level){
// if(f==0&&u==0)
// {	return ;}
FOR(i,0,26){
	ll k=tr[u][i];
	if(k!=0){
	if(en[k]!=0){

		ll po=0;
		for(auto j:z[u]){
			//cout<<j<<endl;
			ll sz=v[j].size();
			ll mo=c[j][sz-1][i];
			if(level-1>=0)
				mo-=c[j][level-1][i];
			if(mo>0)po++;
		}
		
		ans+=po-1;
	}
	dfs(k,0,level+1);

}
}

}

int main(){

	#ifndef ONLINE_JUDGE
    // for getting input from input.txt	
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
	 #endif

    FAST
//	PRECISE


cin>>n;
FOR(i,0,n){
cin>>v[i],reverse(v[i].begin(),v[i].end());
ll sz=v[i].size();
ve <ve <ll> > du(sz,ve <ll> (26));
c[i]=du;
FOR(j,0,sz){
	FOR(po,0,26)
	if(j-1>=0)
	c[i][j][po]+=c[i][j-1][po];
	c[i][j][v[i][j]-'a']++;
}

}
FOR(i,0,n){
	add1(v[i],i);
}

dfs(0,1,0);

cout<<ans;

return 0;
 }
 


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

int main(){
	/*input*/
	int r;	cin >> r;
	/*calculation*/
	/*output*/
	if(r < 1200){
		cout << "ABC" << endl;
	}else if(r < 2800){
		cout << "ARC" << endl;  
	}else{
		cout << "AGC" << endl;
	}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
int main(){
	ll n; cin>>n;
	string a,b; cin>>a>>b;
	ll co = 1;
	for(int i = 0; i < n; i++){
		cout<<a[i];
		cout<<b[i];
	}
	
	
	
	
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#define lli long long int
#define uli unsigned long long int
#define inf 999999999999999999
#define rep(i,n,m) for(lli i=(lli)(n);i<(lli)(m);++i)
#define reep(i,n,m) for(int i=(int)(n);i<=(int)(m);++i)
#define per(i,m,n) for(lli i=(int)(m)-1;i>=(int)(n);--i)
#define st(n) sort(n.begin(), n.end())
#define rev(n) reverse(n.begin(),n.end())
#define ou(S) cout << S << endl
using namespace std;
int main(){
  string s;
  cin>>s;
  rep(i,0,3)
    if(s.at(i)==s.at(i+1)){
      ou("Bad");
      return 0;
    }
  ou("Good");
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std; 
int main(){
	//freopen("input.txt","r",stdin);?
	int n; cin>>n; 
	int arr[n];
	for(int i=0;i<n;i++) cin>>arr[i];
	double s=0; 
	sort(arr,arr+n);

	s=arr[0];

	for(int i=1;i<n;i++){
		s=(s+arr[i])/2.0; 
	}

	cout<<s<<endl;
}

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

int main(){
    int N,C;
    cin>>N>>C;
    int Cake[C];
    int total=0;
    for(int i=0;i<C;i++){
        cin>>Cake[i];
        total+=Cake[i];
    }
    cout<<total/(N+1)+(total%(N+1)!=0)<<endl;
    return 0;

}


Measured memory_bytes: 3084
#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
from typing import *
import collections
import functools
import itertools
import math
import sys

INF = float('inf')
YES = "YES"  # type: str
NO = "NO"  # type: str


def list_uniq_count(l):
    return len(set(l))


def solve(N: int, A: "List[int]"):
    return [NO, YES][list_uniq_count(A) == len(A)]


def main():

    sys.setrecursionlimit(10 ** 6)

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(f'{solve(N, A)}')


if __name__ == '__main__':
    main()


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

#define itn int
#define vi vector<int>
#define pb push_back
#define srt sort(v.begin(), v.end())
#define retunr return
#define No cout<<"No"
#define Yes cout<<"Yes"

//int infiint = std::numeric_limits<int>::max();
//float infiflt = std::numeric_limits<float>::infinity();


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

#ifdef _DEBUG
//  			freopen("input.txt", "r", stdin);
//        freopen("output", "w", stdout);
#endif
   
  int a, b;
  cin >> a >> b;
  for(int i=0; i<1e4; i++) {
    if(floor(i*0.08) == a && floor(i*0.1) == b) {
      cout << i;
      return 0;
    }
    
  }       
  cout << -1;

	return 0;
}


Measured memory_bytes: 256