akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define FAST_IO                       \
	ios_base::sync_with_stdio(false); \
	cin.tie(0);                       \
	cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;

const int MOD = 1e9 + 7;

void add_self(int& a, int b)
{
	a += b;
	if (a >= MOD)
	{
		a -= MOD;
	}
}

void sub_self(int& a, int b)
{
	a -= b;
	if (a < 0)
	{
		a += MOD;
	}
}

const int MAXN = 1e3 + 5;


int main()
{

	FAST_IO;
	// dp[k] // the prob that there are k heads so far
	// if we toss i times, k times heads -> i-k times tail s
	int n;
	cin >> n;
	double p;
	vector<double> dp(n + 1);
	dp[0] = 1;
	for (int coin = 0; coin < n; ++coin) {
		cin >> p;
		for (int i = coin + 1; i >= 0; --i) {
			dp[i] = (i == 0 ? 0 : dp[i - 1] * p) + dp[i] * (1 - p);
		}
	}
	double answer = 0.0;
	for (int heads = 0; heads <= n; ++heads) {
		int tails = n - heads;
		if (heads > tails)
			answer += dp[heads];
	}
	printf("%.10lf", answer);
	return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<unordered_map>
#include<queue>
#include<stack>
#include<string>
#include<bitset>
#include<random>
#include<time.h>
#define INF 1000000000ll
#define MOD 1000000007ll
#define EPS 1e-10
#define REP(i,m) for(long long i=0; i<(ll)m; i++)
#define FOR(i,n,m) for(long long i=n; i<(ll)m; i++)
#define DUMP(a) for(long long dump=0; dump<(ll)a.size(); dump++) { cout<<a[dump]; if(dump!=(ll)a.size()-1) cout<<" "; else cout<<endl; }
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v) sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef long double ld;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll a,b,c,x,y;
	cin>>a>>b>>c>>x>>y;
	ll ans=INF*INF;
	REP(i,1000010) {
		ll na=max(0ll,x-i/2);
		ll nb=max(0ll,y-i/2);
		ans=min(ans,i*c+na*a+nb*b);
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 256
s = input()
t = input()

flag = 0
count = 0
new = ''
l = []
for i in range(len(s)):
    if s[i] == '?' or s[i] in t:
        if count == 0:
            start = i
        count += 1
    else:
        if count >= len(t):
            for j in range(count-len(t)+1):
                check = 0
                for k in range(len(t)):
                    if s[start+j+k] != t[k] and s[start+j+k] != '?':
                        check = 1
                        break
                if check == 0:
                    new = s[:start+j] + t + s[start+len(t)+j:]
                    l.append(new)
                    flag = 1
        count = 0

if count >= len(t):
    for j in range(count-len(t)+1):
        check = 0
        for k in range(len(t)):
            if s[start+j+k] != t[k] and s[start+j+k] != '?':
                check = 1
                break
        if check == 0:
            new = s[:start+j] + t + s[start+len(t)+j:]
            l.append(new)
            flag = 1

if flag == 0:
    print('UNRESTORABLE')
else:
    ans = []
    for n in l:
        for i in range(len(n)):
            if n[i] == '?':
                n = n[:i] + 'a' + n[i+1:]
        ans.append(n)
    print(sorted(ans)[0])


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

using namespace std;
using ll = long long;

const int N = 100005;

int main() {
	int k;
	scanf("%d", &k);
	ll ans = 0;
	for(int a = 1; a <= k; a++) {
		for(int b = 1; b <= k; b++) {
			int g = __gcd(a, b);
			for(int c = 1; c <= k; c++) {
				ans += __gcd(g, c);
			}
		}
	}
	printf("%lld\n", ans);
}


Measured memory_bytes: 3748
// D - Decrease (Contestant ver.)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
	ll K; cin>>K;
	ll N = 50;
	cout<< N <<endl;
	for(ll i=1; i<=N; ++i)
		cout<< (N-i) + (N-i+K)/N <<" ";
}

Measured memory_bytes: 256
import java.util.Scanner

object Main{
  val sc = new Scanner(System.in)
  def main(args: Array[String]): Unit ={

    val n = sc.nextInt
    val m = sc.nextInt


    val l = (1 to n).foldLeft(List.empty[List[Int]]) {(seq, i) =>
      val k = sc.nextInt
      seq :+ List.fill(k)(sc.nextInt)
    }

    val c = l.foldLeft((1 to m).toList)( _ intersect _)

    println(c.size)

  }

}

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

namespace Atcoder
{
    class AtCodeeeeeeeeeeeeeeeeeeeer
    {
        static void Main(string[] args)
        {
            string O = Console.ReadLine();
            string E = Console.ReadLine();
            string ans = "";
            for (int i = 0; i < O.Length+E.Length; i++)
            {
                if (i%2==0)
                {
                    ans += O[i/2];
                }
                else
                {
                    ans += E[i/2];
                }
            }
            Console.WriteLine(ans);
        }

    }
}


Measured memory_bytes: 11092
// SeeAlso: 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define MAX 100000
#define NIL -1
#define MOD 1000000007

typedef int _loop_int;
#define rep(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define debug(x) cout<<#x<<": "<<x<<endl
#define debig_vec(v) cout<<#v<<":";rep(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

// 最大公約数
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
// 最小公倍数
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}

#define print2D(h, w, arr) rep(i, h) { rep(j, w) cout << arr[i][j] << " "; cout << endl; }
template<class T> void print(const T& x){cout << setprecision(12) << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }

ll n, m;
multimap<ll, ll> mm;
ll h[100002];

int main() {
    
    cin >> n >> m;
    
    rep(i, n) {
        cin >> h[i];
    }
    
    rep(i, m) {
        ll a,b;
        cin >> a >> b;
        mm.insert(make_pair(a-1, b-1));
        mm.insert(make_pair(b-1, a-1));
    }

    ll ans = 0;

    rep(i, n) {
        if (h[i]==-1) continue;
        ll currentH = h[i];
        auto ret = mm.equal_range(i);
        bool flag = true;

        if (ret.first==ret.second) {
            ans++;
            continue;
        }

        for(auto it = ret.first; it !=ret.second;it++) {
            ll nextI = it->second;
            if(h[nextI]<currentH) {
            } else {
                flag = false;
            }
        }

        if (flag) {
            ans++;
        }
    }

    print(ans);
    return 0;
}


Measured memory_bytes: 16840
A,B,M = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
x = []
y = []
c = []
for _ in range(M):
    X,Y,Z = map(int,input().split())
    x.append(X)
    y.append(Y)
    c.append(Z)

mini = min(a) + min(b)
for i in range(M):

    rei = a[x[i]-1]
    den = b[y[i]-1]
    coop = c[i]

    if rei + den - coop < mini:
        mini = rei + den - coop

print(mini)


Measured memory_bytes: 30688
"""
"""


def int_as_array(num): return list(map(int, [y for y in str(num)]))


def array_as_int(arr): return int(''.join(map(str, arr)))


def read_int(): return int(input())


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


def array_to_string(arr, sep=' '): return sep.join(map(str, arr))


def matrix_to_string(arr, sep=' '): return '[\n' + '\n'.join(
    [sep.join(map(str, row)) for row in arr]) + '\n]'


def solve(L):
    return (L / 3) ** 3


L = read_int()
print(solve(L))


Measured memory_bytes: 3064
#include "bits/stdc++.h"
using namespace std;
#define repr(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repr(i,0,n)
#define reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define PI 3.1415926535
typedef long long ll;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<Pll> vPll;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
typedef vector<vector<double>> vvd;
typedef vector<vector<Pi>> vvPi;
typedef priority_queue<int, vector<int>, greater<int>> pqli;
typedef priority_queue<ll, vector<ll>, greater<ll>> pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi>> pqlP;
string YN(bool y) { return (y?"YES":"NO"); }
string yn(bool y) { return (y?"Yes":"No"); }
string ON(bool y) { return (y?"OK":"NG"); }
int main(void)
{
	int n;

	cin>>n;

	vi v(n), c(n), d(n);

	rep(i, n) cin>>v[i];

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

	sort(all(d));

	int ans=0;
	rep(i, n){
		if(d[i]>0) ans+=d[i];
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 256
from itertools import product
h,w,k=map(int,input().split())
a=0
c=[[0 if l=='.' else 1 for l in input()] for _ in range(h)]
for i in product([0,1] , repeat=h):
  for j in product([0,1] , repeat=w):
    b=0
    for H,W in product(range(h),range(w)):
      b+=c[H][W]*i[H]*j[W]
    if b == k:
      a+=1
print(a)

Measured memory_bytes: 9128
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int x = sc.nextInt();
if(x>=a&&x<=a+b){
System.out.println("YES");
}else{
	System.out.println("NO");
}
	}}

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

int main() {
    int n;cin>>n;
    vector<int> a(n);
    for (auto& v : a) cin>>v;
    
    int f = 1;
    int count = 1;
    
    rep(i,a.size()) {
        f = a.at(f-1);
        if (f==2) {
            cout << count << endl;
            return 0;
        }
        count++;
    }
    
    cout << -1 << endl;
}



Measured memory_bytes: 640
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
MOD = 1000000007
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

N,A,B=LI()

print(min(N*A,B))


Measured memory_bytes: 3064
//temp##############################################

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void strInit(char str[]);//str[]を0で初期化
void extIntStr(char str[],int data[]);//str[]から数値(int)を抽出しdata[]に順次格納
void incsort(int data[],int len);//data[]を昇順ソート
void decsort(int data[],int len);//data[]を降順ソート
void printIntArray(int data[],int len);//data[]をprint
int* inputArray(int n);//文字列を受け取り数値を抽出、n個の数値(int)を格納した配列のポインタをreturn
int* cpyArray(int data[],int len);//配列(int)を複製した配列のポインタをreturn

void strInit(char str[]){
    int len=strlen(str);
    for(int i=0;i<len;i++){
        str[i]=0;
    }
}

void extIntStr(char str[],int data[]){
    int length=strlen(str);
    str[length-1]=' ';
    char buff[12];
    int j,index;
    index=j=0;
    for(int i=0;i<length;i++){
        if(str[i]!=' '){
            buff[j++]=str[i];
        }else{
            data[index++]=atoi(buff);
            strInit(buff);
            j=0;
        }
    }
}

void incsort(int data[],int len){
    for(int i=0;i<len-1;i++){
        for(int j=i+1;j<len;j++){
            if(data[i]>data[j]){
                int tmp=data[i];
                data[i]=data[j];
                data[j]=tmp;
            }
        }
    }
}

void decsort(int data[],int len){
    for(int i=0;i<len-1;i++){
        for(int j=i+1;j<len;j++){
            if(data[i]<data[j]){
                int tmp=data[i];
                data[i]=data[j];
                data[j]=tmp;
            }
        }
    }
}

void printIntArray(int data[],int len){
    for(int i=0;i<len;i++){
        printf("%d\n",data[i]);
    }
}

int* inputArray(int n){
    int *data;
    data=(int*)malloc(sizeof(int)*n);
    char *get;
    get=(char*)malloc(sizeof(char)*11*n+1);
    fgets(get,11*n+1,stdin);
    extIntStr(get,data);
    free(get);
    return data;
}

int* cpyArray(int data[],int len){
    int *cp;
    cp=(int*)malloc(sizeof(int)*len);
    for(int i=0;i<len;i++){
        cp[i]=data[i];
    }
    return cp;
}

//temp##############################################

//don't forget free(data);

int main(){
    int n,d;
    scanf("%d %d",&n,&d);
    int ans=(n+2*d)/(2*d+1);
    printf("%d",ans);
    return 0;
}

Measured memory_bytes: 128
N = int(input())

if N % 2 == 0:
    Ans = 0
    p = 1
    check = 0
    while check != 0 or p == 1:
        check = N // (2 * 5**p)
        Ans += check
        p += 1
    print(Ans)

else:
    print(0)

Measured memory_bytes: 9072
N = int(input())

A = list(map(int,input().split()))

i = 0
res = 0
while  i < N:
    while i+1 < N and A[i] == A[i+1]: i += 1

    if i+1 < N and A[i] <= A[i+1]:
        while i+1 < N and A[i] <= A[i+1]: i += 1
    elif i+1 < N and A[i] >= A[i+1]:
        while i+1 < N and A[i] >= A[i+1]: i += 1
    res += 1
    i += 1
print(res)


Measured memory_bytes: 20368
#!python3

LI = lambda: list(map(int, input().split()))

# input
N = int(input())
A = LI()


def main():
    if 0 in A:
        print(0)
        return
    x = 1
    t = 10 ** 18
    for a in A:
        x *= a
        if x > t:
            print(-1)
            return
    print(x)


if __name__ == "__main__":
    main()


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

#define BR "\n"
#define SP " "
#define SHOW(x) for(int i = 0; i < x.size(); i++) { cout << x[i] << SP; } cout << BR;
#define SHOW2(x) for(int j = 0; j < x.size(); j++) { SHOW(x[j]); } cout << BR;

vector<int> A[100000];
int main() {
  ll N, M;
  cin >> N >> M;

  for (int i = 0; i < N; i++) {
    int a, b;
    cin >> a >> b;
    A[a].push_back(b);
  }

  ll ans = 0;
  priority_queue<int> p;
  ll cnt = 0;
  for (int i = 1; i <= M; i++) {
    int d = i;
    cnt += A[d].size();
    if (cnt == 0) continue;

    for (int j = 0; j < A[d].size(); j++) {
      p.push(A[d][j]);
    }
    ans += p.top();
    p.pop();
    cnt--;
  }
  cout << ans << BR;

  return 0;
}

Measured memory_bytes: 5632
import java.util.*;

public class Main {

    public static void main(String[] args) {
        // write your code here
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        int[] union = new int[n];
        for (int i = 0; i < n; i++) {
            union[i] = i;
        }

        for (int i = 0; i < m; i++) {
            union(union, scanner.nextInt() - 1, scanner.nextInt() - 1);
        }

        int[] sum = new int[n];

        for (int i = 0; i < n; i++) {
            sum[find(union, i)]++;
        }
        Arrays.sort(sum);

        System.out.println(sum[n - 1]);
    }

    //return root node idx O(a(N)) ( O(1)<O(a(N))<O(logN) )
    public static int find(int[] tree,int idx) {
        if(tree[idx]==idx) return idx;
        else return tree[idx] = find(tree,tree[idx]);
    }

    //union idx2 tree to idx1 tree O(a(N))
    public static void union(int[] tree,int idx1,int idx2) {
        int root1 = find(tree,idx1);
        int root2 = find(tree,idx2);
        tree[root2] = root1;
    }

}

Measured memory_bytes: 60740
#include<iostream>
int R,C,s[10000][10],f[10],N,i,j,n,m;void rec(int k){if(k==R){for(n=i=0;i<C;i++,n+=m>R-m?m:R-m)for(m=j=0;j<R;j++)m+=s[i][j]^f[j];N=N>n?N:n;return;}f[k]=0;rec(k+1);f[k]=1;rec(k+1);}main(){for(;std::cin>>R>>C,R;rec(0),std::cout<<N<<"\n")for(j=R;j-->0;)for(i=C;i-->0;)std::cin>>s[i][j];}

Measured memory_bytes: 1248
x,y=input().strip().split()
Z=['1','3','5','7','8','10','12']
I=['4','6','9','11']
if x in Z and y in Z:
    print('Yes')
elif x in I and y in I:
    print('Yes')
elif x==y:
    print('Yes')
else:
    print('No')

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

using ll = long long;

int main(){
  long long int a,b,n;
  cin >> a >> b >> n;

  int maxv = 0;
  if(n<b){
    // n<=bってことは[x/b]=0こていなのでAxがクソでかいほうがいいのでは？
    /*long long int A,B;
    for(int i=1;i<=n;i++){
      A = int(a*i/b);
      B = int(i/b);
      maxv = max(maxv, int(A-B*a) );
    }*/
    double A;
    A = double(a*n/b);
    maxv = floor(A);
    cout << maxv << endl;
  }
  else{
    double A,B;
    long long int i = b-1;
      A = double(a*i/b);
      B = double(i/b);
      maxv = max(maxv, int(floor(A)-floor(B)*a) );
    
    cout << maxv << endl;
  }

}

/*
floor は x=nb+m とおくとnによらずmのみで決定する
またmが大きい時差が最大になる
*/

Measured memory_bytes: 3600
use std::io::stdin;
use std::io::BufRead;
use std::io::BufReader;

fn main() {

let mut scan = std::io::stdin();
 
let mut line = String::new();
 
let _ = scan.read_line(&mut line);
 
let vec: Vec<&str> = line.split_whitespace().collect();
 
let a: i32 = vec[0].parse().unwrap_or(0);
let b: i32 = vec[1].parse().unwrap_or(0);
//標準入力を読み込む

let add: i32 = a+b;
let sub: i32 = a-b;
let mul: i32 = a*b;
let mut max: i32 = add;

if sub>max {
    max = sub;
}
if mul>max {
    max = mul;
}

println!("{}", max);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

void _main() {
  int a, b;
  cin >> a >> b;

  if (a <= 0 && 0 <= b) {
    cout << "Zero" << "\n";
    return;
  }
  if (a > 0) {
    cout << "Positive" << "\n";
    return;
  }

  if ((b-a+1)%2 == 0) cout << "Positive" << "\n";
  else              cout << "Negative" << "\n";
}

Measured memory_bytes: 256
#include <stdio.h>
int main()
{
    int a,b,c,d;
    while(scanf("%d %d %d %d",&a,&b,&c,&d)!=EOF)
    {
        int sum=0;
        if(a<b)
            sum=sum+a;
        else
            sum=sum+b;
        if(c<d)
            sum=sum+c;
        else
            sum=sum+d;
        printf("%d\n",sum);
    }
    return 0;
}


Measured memory_bytes: 128
use std::io::*;
use std::str::FromStr;
use std::cmp::{max, min};

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("faild to read char") as char)
        .take_while(|c| !c.is_whitespace())
        .collect();
    token
        .parse()
        .ok()
        .expect("faild to parse token")
}

fn main(){
    let x: u64 = read();
    let y: u64 = read();

    if (x + y) % 3 != 0 {
        println!("0");
        return;
    }

    let sum = (x + y) / 3;
    let sub = max(x, y) - min(x, y);
    if min(x, y) < sum {
        println!("0");
        return;
    }
    let c = (sum + sub) / 2;
    let d = (sum - sub) / 2;
    //println!("{} {}", c, d);
    // println!("{} {}", sum, sub);

    let mut ret = 1;
    for i in 0..c {
        ret = (ret * (d + c - i)) % MOD;
        //println!("{}", ret);
        ret = (ret * inverse(i + 1)) % MOD;
        //println!("{}", ret);
        //println!("{}", inverse(d + c - i) * (d + c - i) % MOD);
        //println!("{} {}", ret, i);
    }
    println!("{}", ret);
}

const MOD: u64 = 1000000007;

fn pow(base: u64, exp: u64) -> u64 {
    if exp == 1 {
        return base;
    } else if exp == 0 {
        return 1;
    } else if exp % 2 == 0 {
        let prev = pow(base, exp / 2);
        return (prev * prev) % MOD;
    } else {
        let prev = pow(base, exp / 2);
        return (((prev * prev) % MOD) * base) % MOD;
    }
}

fn inverse(n: u64) -> u64 {
    pow(n, MOD - 2)
}


Measured memory_bytes: 4352
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;

#define REP(i, n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i, n) for(ll i=(ll)(n-1);i>=0;i--)
#define FOR(i, a, b) for(ll i=(ll)(a); i<=(ll)(b); i++)
#define RFOR(i, a, b) for(ll i=(ll)(a);i>=(ll)(b); i--)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define INF 1000000000000
#define MOD 10000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

signed main()
{
	ll K;
	cin >> K;
	ll mod=7%K;
	bool exist = false;
	int count=1;
	REP(i, K){
		if(mod==0){
			exist = true;
			break;
		}
		mod = (mod*10+7)%K;
		count++;
	}
	if(exist){
		cout << count << endl;
	}else{
		cout << -1 << endl;
	}
}


Measured memory_bytes: 3632
#include<stdio.h>
int main()
{  int n,a[200001]={0},i,x;
   scanf("%d",&n);
   for(i=0;i<n-1;i++)
   {  scanf("%d",&x);
      a[x]++;
   }
   for(i=1;i<=n;i++)
   printf("%d\n",a[i]);
}

Measured memory_bytes: 2516
a, b, c = map(int,input().split())
ans = 0
if a == b == c:
  if a % 2 == 0:
    print(-1)
  else:
    print(0)
  exit()
else:
  while True:
    if a % 2 == 0 and b % 2 == 0 and c % 2 == 0:
      ans += 1
      p = a // 2
      q = b // 2
      r = c // 2
      a = q + r
      b = r + p
      c = p + q
    else:
      break

print(ans)


Measured memory_bytes: 3060
#pragma region header
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <math.h>
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rev(i, n) for(int i = (int)(n - 1); i >= 0; i--)
#define rev1(i, n) for(int i = (int)(n); i > 0; i--)
#define pb push_back
#define ts to_string
#define all(v) (v).begin(), (v).end()
#define vi vector<int>
#define vvi vector<vector<int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vs vector <string>
#define vvs vector <vector<string>>
#define pq  priority_queue<int>
using ll = long long;
/* ----------------よく使う数字や配列----------------- */
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
constexpr ll mod = 1e9 + 7;
constexpr long double pi = 3.141592653589793238462643383279;
/* ----------------------end----------------------- */
/* --------------------ライブラリ-------------------- */
ll fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i % mod;
}
ll gcd(ll a, ll b) {        //最大公約数
    if (b == 0) return a;
    return gcd(b, a % b);
}
ll lcm(ll a, ll b) {      //最小公倍数
    return a * b / gcd(a, b);
}
bool isprime(ll a)//素数判定、primeならtrue,違うならfalse
{
    if (a < 2) return false;
    else if (a == 2) return true;
    else if (a % 2 == 0) return false;
    double m = sqrt(a);
    for (int i = 3; i <= m; i += 2)
    {
        if (a % i == 0)
        {
            return false;
        }
    }
    // 素数である
    return true;
}
ll ketasum(ll n) {    //各桁の和
    ll sum = 0;
    while (n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
ll kind(vi SYURUI) {//vector<int>型の配列の要素の種類数
    int size = SYURUI.size();
    sort(all(SYURUI));
    int cnt = 1;
    rep(i, size-1) {
        if (SYURUI[i] != SYURUI[i + 1])cnt++;
    }
    return cnt;
}
/* ----------------------end----------------------- */
#pragma endregion
signed main() {
    string A, B; cin >> A >> B;
    string C = A + B;
    int N = stoi(C);
    if (fmod(sqrt(N), 1.0) == 0)puts("Yes");
    else puts("No");
}





Measured memory_bytes: 3736
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

string S,T;
int x[10000],y[10000];
int dp[10000][10000];
char U[53]="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
int MAXN;

int main(){
	int q;
	cin>>q;
	for(int i=0;i<q;i++){
		MAXN=0;
		cin>>S>>T;
		for(int i=0;i<S.size();i++){
			for(int j=0;j<52;j++){
				if(S[i]==U[j]){
					x[i+1]=j;
				}
			}
		}
		for(int i=0;i<T.size();i++){
			for(int j=0;j<52;j++){
				if(T[i]==U[j]){
					y[i+1]=j;
				}
			}
		}
		for(int i=0;i<=T.size();i++){
			for(int j=0;j<=S.size();j++){
				if(i==0 || j==0){
					dp[i][j]=0;
				}
				else if(x[j]==y[i]){
					dp[i][j]=dp[i-1][j-1]+1;
				}
				else{
					dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
				}
			}
		}
		for(int i=0;i<=T.size();i++){
			for(int j=0;j<=S.size();j++){
				MAXN=max(MAXN,dp[i][j]);
			}
		}
		cout<<MAXN<<endl;
	}
	return 0;
}


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

int main(){
    long long N;
    cin >> N;
    long long n, h, w;

    for(h = 1; h <= 3500; h++){
        for(w = 1; w <= 3500; w++){
            if( 4*h*w - N*w - N*h > 0 and (N*h*w) % (4*h*w - N*w - N*h) == 0){
                //printf("4*h*w - N*w - N*h %lld\n", 4*h*w - N*w - N*h);
                n = N*h*w/(4*h*w - N*w - N*h);
                printf("%lld %lld %lld\n", h, n, w);
                return 0;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 3768
raw_input_arr = STDIN.read.split("\n")
num_blue_cards = raw_input_arr[0].to_i
num_red_cards = raw_input_arr[num_blue_cards + 1].to_i
blue_cards = raw_input_arr.slice(1, num_blue_cards)
red_cards = raw_input_arr.slice(num_blue_cards + 2, num_red_cards)

h = Hash.new(0)
blue_cards.each { |word| h[word] += 1 }
red_cards.each { |word| h[word] -= 1 }
max_reward = [h.max_by { |_, v| v }[1], 0].max
puts max_reward

Measured memory_bytes: 1788
#include<iostream>
#include<algorithm>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)

const int N = 6000;
bool block[N][5];

void all_fall(int y){
  rep(j,5)block[y][j]=false;
  REP(i,y,N-1){
    rep(j,5)block[i][j]=block[i+1][j];
  }
  rep(j,5)block[N-1][j]=false;
}

int getmax(int l,int r){
  int ret=0;
  REP(j,l,r){    
    int tmp = N-1;
    for(int i=N-1;i>=0;i--){
      if (block[i][j])break;
      tmp=i;
    }
    ret=max(ret,tmp);
  }
  return ret;
}

void fall(){
  rep(i,N){
    if (block[i][0]&block[i][1]&block[i][2]&block[i][3]&block[i][4]){
      all_fall(i);
      i--;
    }
  }
}

main(){
  int n;
  while(cin>>n && n){
    rep(i,N)rep(j,5)block[i][j]=false;
    rep(i,n){
      int d,p,q;
      int wid=1,hei=1,pos;
      cin>>d>>p>>q;
      q--;
      if (d == 1){//yoko
	pos = getmax(q,q+p);	
	wid=p;
      }else if (d == 2){//tate
	pos = getmax(q,q+1);
	hei=p;
      }

      rep(i,hei){
	rep(j,wid){
	  block[pos+i][q+j]=true;
	}
      }
      fall();
    }

    cout << count(&block[0][0],&block[N][0],true) << endl;
  }
}

Measured memory_bytes: 0
import random
import copy
import time
def evaluateSatisfaction(d, c, s, ans):
    score = 0
    last = [-1 for i in range(26)]
        
    for i in range(d):
        
        score += s[i][ans[i]]
        last[ans[i]] = i
        for j in range(26):
            if j != ans[i] or True:
                score -= c[j]*(i - last[j])
    return score
    
def valuationFunction(d,c,s,contestType,day,last):
    las = copy.copy(last)
    las[contestType] = day
    gain = s[day][contestType]
    lost = 0
    for i in range(10):
        for j in range(26):
            lost += c[j]*(i - las[j])
    return gain - lost

def Input():
    d = int(input())
    c = list(map(int, input().split()))
    s = [list(map(int, input().split())) for i in range(d)]
    #s[3][25] =   contest(25+1) of day(3+1)
    return d, c, s

def evolution(d, c, s, ans):
    score_before = evaluateSatisfaction(d, c, s, ans)
    ans_after = copy.copy(ans)
    x = random.randint(0,(d-1)-10)
    idx1 = x
    idx2 = x+random.randint(0,5)
    
    tmp = ans_after[idx1]
    ans_after[idx1] = ans_after[idx2]
    ans_after[idx2] = tmp

    score_after = evaluateSatisfaction(d,c,s,ans_after)

    if score_after > score_before:
        return ans_after
    else:
        return ans

if __name__ == "__main__":
    
    d, c, s = Input()
    
    #print("val =", evaluateSatisfaction(d, c, s, [1, 17, 13, 14, 13]))

    #calc start
    t1 = time.time()
    ans = [0 for i in range(d)]
    last = [-1 for i in range(26)]
    for i in range(d):
        evalValueList = [0 for j in range(26)]
        for j in range(26):
            evalValueList[j] = valuationFunction(d, c, s, j,i,last)

        max_idx = 0
        max = evalValueList[0]

        for j in range(26):
            if (max < evalValueList[j]):
                max_idx = j
                max = evalValueList[j]
        
        ans[i] = max_idx
        last[ans[i]] = i


    
    #ans = [1, 2, 3, 4, 5]
    t2 = time.time()
    while(float(t2-t1) < 1.8):
        ans = evolution(d, c, s, ans)
        #print("ans = ",evaluateSatisfaction(d,c,s,ans))
        t2 = time.time()
    for x in ans:
        print(x + 1)
    #print(evaluateSatisfaction(d,c,s,ans))

Measured memory_bytes: 10068
#include<iostream>
using namespace std;
typedef long long ll;
int main(){
  ll n,k,df,ans,tmp;
  cin >> n >> k;
  ll a[n],psum[n],sum[n];
  fill(sum,sum+n,0);
  fill(psum,psum+n,0);
  ans = -10000000000000;
  for(int i=0;i<n;i++){
    if(i!=0){
      psum[i]=psum[i-1];
      sum[i]=sum[i-1];
    }
    cin >> a[i];
    sum[i]+=a[i];
    psum[i]+=max((ll)0,a[i]);
  }
  for(int i=0;i+k<=n;i++){
    df=i+k-1;
    tmp=0;
    if(i!=0){
      tmp+=psum[i-1];
      tmp+=max(sum[df]-sum[i-1],(ll)0);
    }else{
      tmp+=max(sum[df],(ll)0);
    }
    if(df!=n-1){
      tmp+=psum[n-1]-psum[df];
    }
    ans = max(tmp,ans);
  }
  cout << ans << endl;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
// typedef
using ll  = long long;
using str = string;
using PL  = pair<ll, ll>;
using P   = pair<int, int>;
using VL  = vector<ll>;
using VI  = vector<int>;
using VS  = vector<str>;
using VP  = vector<P>;
using VPL = vector<PL>;
using VVL = vector<VL>;
using VVI = vector<VI>;

// const num
const ll INF         = 1e18 + 18;
const ll MAX         = 100005;
const ll MOD         = 1000000007;
const long double PI = acosl(-1.0);

// loop
#define REP(i, a, b) for(ll(i) = (a); (i) < (b); (i)++)
#define RREP(i, a, b) for(ll(i) = (a); (i) >= (b); (i)--)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) RREP(i, n, 0)

// YesNo
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
// All
#define ALL(v) v.begin(), v.end()
#define deduplicate(v) (v).erase(unique(ALL(d)), (v).end())

int main(void) {
	ll x, k, d;
	ll ans;
	cin >> x >> k >> d;
	x    = abs(x);
	ll n = x / d;
	if(x == d) {
		if(k % 2 == 0) {
			ans = abs(x);
		} else {
			ans = 0;
		}
	} else if(n == 0) {
		if(k % 2 == 0) {
			ans = abs(x);
		} else {
			ans = abs(x - d);
		}
	} else if(n >= k) {
		ans = abs(x - k * d);
	} else {
		if((k - n) % 2 == 1) {
			ans = abs(x - (n + 1) * d);
		} else {
			ans = abs(x - n * d);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3568
#@profile
def dfs(p,s,c,cmin,cmax):
    if len(p) == 0:
        return solve(s,c,cmin,cmax)
    lower, u = p[0]
    c += lower
    if u <= 9:
        cmin[lower] = 0
        cmax[lower] = u
        return dfs(p[1:],s,c,cmin,cmax)
     
    cmin[lower] = 0
    cmax[lower] = 9
    ret = dfs(p[1:],s,c,cmin,cmax)
 
    upper = lower.upper()
    s = s.translate(str.maketrans({lower:upper + lower}))
 
    c += upper
    if u % 10 == 9:
        cmin[upper] = 1
        cmax[upper] = u // 10
        return ret + dfs(p[1:],s,c,cmin,cmax)
    if 20 <= u:
        cmin[upper] = 1
        cmax[upper] = u // 10 - 1
        ret += dfs(p[1:],s,c,cmin,cmax)
    cmin[lower] = 0
    cmax[lower] = u % 10
    cmin[upper] = u // 10
    cmax[upper] = u // 10
    return ret + dfs(p[1:],s,c,cmin,cmax)
#@profile
def solve(s,c,cmin,cmax):
    uf = [-1] * 128
    s1 = map(ord,s[:len(s)//2])
    s2 = map(ord,s[::-1][:len(s)//2])
    for p,q in zip(s1,s2):
        p = root(uf,p)
        q = root(uf,q)
        if p != q:
            if uf[p] >= uf[q]:
                uf[p] += uf[q]
                uf[q] = p
            else:
                uf[q] += uf[p]
                uf[p] = q

    nmin,nmax = {},{}
    for ci in c:
        p = root(uf,ord(ci))
        p = str(p)
        try:
            nmax[p] = min(nmax[p],cmax[ci])
            nmin[p] = max(nmin[p],cmin[ci])
        except KeyError:
            nmax[p] = cmax[ci]
            nmin[p] = cmin[ci]
     
    ret = 1
    for p in nmax.keys():
        if nmax[p] < nmin[p]:
            return 0
        ret *= nmax[p] - nmin[p] + 1
    return ret
    
#@profile 
def root(uf,p):
    if uf[p] < 0:
        return p
    uf[p] = root(uf,uf[p])
    return uf[p]

import sys
f = sys.stdin
 
_, _ = map(int, f.readline().split())
s = f.readline().strip()
p = [line.split() for line in f]
for pi in p:
    pi[1] = int(pi[1])
cmin,cmax = {str(i):i for i in range(10)},{str(i):i for i in range(10)}
characters = '0123456789'
print(dfs(p,s,characters,cmin,cmax) % (10 ** 9 + 7))

Measured memory_bytes: 6896
import sys
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
plus, minus = [], []
for _ in range(n):
	s = input()
	mi, cur = 0, 0
	for i in range(len(s)):
		if s[i] == "(":
			cur += 1
		else:
			cur -= 1
		mi = min(mi, cur)
	if cur >= 0:
		plus.append((mi, cur))
	else:
		minus.append((mi, cur))

plus.sort(key=lambda x: -x[0])
minus.sort(key=lambda x: x[0] - x[1])
res = plus + minus

cur = 0
for m, t in res:
	if cur + m < 0:
		print("No")
		exit()
	cur += t

if cur != 0:
	print("No")
	exit()
print("Yes")

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

#define ll long long
#define p_q priority_queue
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)


int main(){
    ll h,n;
    cin>>h>>n;

    vector<ll> a(n);
    vector<ll> b(n);

    vector<ll> dp(h+1,100000000);
    dp.at(0) = 0;
    rep(i,n){
        cin>>a.at(i)>>b.at(i);
    }


    for(int i=1;i<=h;i++){
        rep(j,n){
            if(i>=a.at(j)){
                dp.at(i) = min(dp.at(i-a.at(j))+b.at(j),dp.at(i));
            }else{
                dp.at(i) = min(dp.at(i),b.at(j));
            }
        }
    }

     cout<<dp.at(h)<<endl;

}





Measured memory_bytes: 384
/*
 * @Author: BilyHurington
 * @Date: 2020-07-31 21:33:19
 * @LastEditors: BilyHurington
 * @LastEditTime: 2020-07-31 22:30:47
 */ 
#include<bits/stdc++.h>
using namespace std;
int n;char s[300010];
int f[300010][3][3];
const int mod=1e9+7;
void Add(int &x,int y){x+=y;if(x>=mod) x-=mod;}
void Del(int &x,int y){x-=y;if(x<0) x+=mod;}
int main(){
    scanf("%s",s+1);n=strlen(s+1);
    f[0][0][0]=1;
    for(int i=1;i<=n;i++){
        if(s[i]=='0'){
            for(int j=0;j<3;j++){
                for(int k=0;k<3;k++){
                    if(k<2) Add(f[i][j][k+1],f[i-1][j][k]);
                    else Add(f[i][j][k-1],f[i-1][j][k]);
                }
            }
        }
        if(s[i]=='1'){
            for(int j=0;j<3;j++){
                for(int k=0;k<3;k++){
                    if(k>0) Add(f[i][j][k-1],f[i-1][j][k]);
                    else if(j==2) Add(f[i][j][k],f[i-1][j][k]);
                    else Add(f[i][j+1][k],f[i-1][j][k]);
                }
            }
        }
        if(s[i]=='?'){
            for(int j=0;j<3;j++){
                for(int k=0;k<3;k++){
                    if(k<2) Add(f[i][j][k+1],f[i-1][j][k]);
                    else Add(f[i][j][k-1],f[i-1][j][k]);
                }
            }
            for(int j=0;j<3;j++){
                for(int k=0;k<3;k++){
                    if(k>0) Add(f[i][j][k-1],f[i-1][j][k]);
                    else if(j==2) Add(f[i][j][k],f[i-1][j][k]);
                    else Add(f[i][j+1][k],f[i-1][j][k]);
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<3;i++) for(int j=0;j<=i;j++) Add(ans,f[n][i][j]);
    printf("%d",ans);
    return 0;
}

Measured memory_bytes: 14632
#include <bits/stdc++.h>
using namespace std;
#define long int64_t

int main() {
	ios_base::sync_with_stdio( false );

	vector<long> a( 3 );
	cin >> a[0] >> a[1] >> a[2];
	sort( a.begin(), a.end() );

	long x = a[0] * a[1] * (a[2]/2);
	long y = a[0] * a[1] * (a[2] - a[2]/2);
	cout << y-x << endl;

	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int a, b, c, d, e;
    scanf("%d %d", &a, &b);
    c= a+b; d= a-b; e= a*b;
    if(c>=d && c>=e) printf("%d\n", c);
    else if(d>=c && d>=e) printf("%d\n", d);
    else printf("%d\n", e);
}


Measured memory_bytes: 1716
n = int(input())
abc = [[0, 0, 0]]
for _ in range(n):
    a, b, c = (int(x) for x in input().split())
    abc.append([a, b, c])
dp = [[0] * 3 for _ in range(n + 1)]
dp[0][0], dp[0][1], dp[0][2] = 0, 0, 0
for i in range(1, n + 1):
    for j in range(3):
        for k in range(3):
            if j != k:
                dp[i][j] = max(dp[i][j], dp[i - 1][k] + abc[i][j])
print(max(dp[n]))

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

int main(){
    int n;
    cin>>n;
    string s;
    int a[n][26]={};
    for(int i=0;i<n;i++){
        cin>>s;
        for(auto j:s){
            a[i][j-'a']++;
        }
    }

    int ans[26];
    for(int i=0;i<26;i++){
        ans[i]=1e5;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<26;j++){
            ans[j]=min(ans[j],a[i][j]);
        }
    }
    bool ng=true;
    string res="";
    for(int i=0;i<26;i++){
        if(ans[i]!=0) ng=false;
        for(int j=0;j<ans[i];j++){
            res+=(char)(i+'a');
        }
    }

    if(ng){
        cout<<""<<endl;
        return 0;
    }

    cout<<res;

}

Measured memory_bytes: 256
#!/usr/bin/perl

my ($d,$n) = map {$_ - 0} split(/\s+/o,<STDIN>);

$b = 1;
$b = 100 if $d == 1;
$b = 10000 if $d == 2;

$n += 1 if $n == 100;

$n *= $b;
print "$n\n";

exit(0);



Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define int long long
#define double long double
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
#define INF 1000000000000000000
using namespace std;

signed main(){
    int n; cin>>n;
    if(n==0){
        cout<<0<<endl;
        return 0;
    }
    int i=1;
    string s="";
    while(n!=0){
        if(n%(i*(-2))!=0){
            n-=i;
            s+='1';
        }
        else s+='0';
        i*=(-2);
    }
    reverse(all(s));
    cout<<s<<endl;
}

Measured memory_bytes: 256
x1, x2, x3, x4 = map(int, raw_input().split())
n = int(raw_input())
ans = 0
if x1 + x1 < x2:
	x2 = x1 + x1
if x2 + x2 < x3:
	x3 = x2 + x2
if x3 + x3 < x4:
	x4 = x3 + x3
n = n * 4
k = n // 8
ans += k * x4
n = n - k * 8
k = n // 4
ans += k * x3
n -= k * 4
k = n // 2
ans += k * x2
n -= k * 2
ans += k * x1
print ans

Measured memory_bytes: 2568
#include <cstdio>
#include <climits>
#include <cassert>
#include <cmath>
#include <iostream>
#include <string>
#include <algorithm>
#include <numeric>
#include <functional>
#include <tuple>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <vector>
#include <iterator>
#include <regex>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define FOR(x,xs) for(auto &x: xs)

using namespace std;
typedef long long ll;
typedef pair<int,int> PI;
typedef pair<ll,ll> PL;
typedef vector<int> VI;
typedef vector<ll> VL;

template <class T, template <class, class> class C, class charT = char>
void vdump(const C<T, allocator<T>> &v, const charT* delimiter = ", ",
           ostream &stream = cout) {
  copy(v.begin(), v.end(), ostream_iterator<T>(stream, delimiter));
  stream << endl;
}

bool reachable(const VI &set, int x) {
  if(set.size() == 0) {
    return x == 0;
  }
  int sum = accumulate(set.begin(), set.end(), 0);
  if(sum < x || sum + x < 0) {
    return false;
  }
  vector<vector<bool>> dp(set.size()+1, vector<bool>(sum*2+1, false));
  dp[0][sum] = true;
  REP(i,0,set.size()) {
    REP(j,0,sum*2+1) {
      int x1 = j - set[i];
      int x2 = j + set[i];
      dp[i+1][j] = (x1 >= 0 && dp[i][x1]) || (x2 <= sum * 2 && dp[i][x2]);
    }
  }
  return dp[set.size()][sum+x];
}

int main() {
  ios::sync_with_stdio(false);

  string s;
  cin >> s;
  int l = s.size();
  int x, y;
  cin >> x >> y;
  vector<VI> ops(2);
  int sx = 0;
  while(sx < l && s[sx] == 'F') sx++;
  x -= sx;
  int dir = 0;
  int d = 0;
  REP(i,sx,l) {
    if(s[i] == 'T') {
      if(d > 0) {
        ops[dir].push_back(d);
        d = 0;
      }
      dir = 1 - dir;
    } else {
      d++;
    }
  }
  if(d > 0) {
    ops[dir].push_back(d);
    d = 0;
  }
  cout << (reachable(ops[0], x) && reachable(ops[1], y) ? "Yes" : "No") << endl;
  
  return 0;
}


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

int main(){
  int w,h;
  cin >> h >> w;
  vector<vector<char>>hyo(h,vector<char>(w));
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin >> hyo.at(i).at(j);
    }
  }
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(hyo.at(i).at(j)=='.'){
        int su=0;
        for(int k=i-1;k<i+2;k++){
          for(int l=j-1;l<j+2;l++){
            if(k>=0&&k<h&&l>=0&&l<w)
            if(hyo.at(k).at(l)=='#')
              su++;
          }
        }
        hyo.at(i).at(j)=su+48;
      }
    }
  }
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cout << hyo.at(i).at(j);
    }
    cout << endl;
  }
}

Measured memory_bytes: 3636
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <deque>
#include <cctype>
#include <unordered_map>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<long, long>;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
#define rep(i, n) for(int i = 0; i<n; i++)
#define rep_s(i, start, n) for(int i= start;  i<n; i++)
#define rep_down(i, n) for(int i = n-1; i>=0; i--)
#define rep_down_s(i, n, start) for(int i = n-1; i>=start; i--)
#define ALL(a) (a).begin(), (a).end()
#define ALL_str(a) (a).cbegin(), (a).cend()

string alphabet_upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string alphabet_lower  = "abcdefghijklmnopqrstuvwxyz";
string numbers = "0123456789";
/*
for (iterator = hash.begin(); iterator != hash.end(); iterator++)
{
// ここで、要素毎の操作を行います。
std::pair<std::string, CMyClass> element = *iterator;

}
*/
/*
using edge = struct {int to; ll cost;};
vector<edge> tree[limit];
ll depth[limit];

void dfs(int v, int p, ll d){
  depth[v] = d;
  //cout <<"v: " << v << endl;
  for (auto &e: tree[v]){
    //cout << "e.to: " << e.to << endl;
    if (e.to == p) continue;
    dfs(e.to, v, d+e.cost);
  }
}
*/
int keta_sum(int num){
  int dig, sum = 0;
  while(num){
    dig = num % 10;
    sum = sum + dig;
    num = num / 10;
  }
  return sum;
}

ll binary_search(ll left_key, ll border, ll low, ll high) {
     // 配列 a の左端と右端
    ll mid = (low+high)/2;
    while (high > low+1) {
       mid = (low+high)/2;
        if (left_key*mid>border) high = mid;
        else if (left_key*mid<border) low = mid;
        else {
          mid =mid-1;
          break;
        }
    }
    return mid;
}

bool IsPrime(ll a){
  ll b = sqrt(a);
  b++;
  while(b-->=2){
    if (a%b==0) return false;
  }
  return true;
}

ll gcd(ll a, ll b){
  ll tmp;
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }

  ll r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main(void){
  ll N, M, A, B, C, D, E, F, K,W, H, Q, R, X, Y;
  ll ans;
  string S, T;
  cin >> R >> D >> X;
  rep(i, 10){
    X = R*X - D;
    cout << X << endl;
  }
  


}


Measured memory_bytes: 256
def main():
    num, wariai_a, wariai_b = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(num)]

    inf = 100 * num + 1
    dp = [[[inf for i in range(400)] for j in range(400)] for k in range(num + 1)]
    dp[0][0][0] = 0
    for i in range(1, num + 1):
        a, b, c = data[i - 1]
        for j in range(400):
            for k in range(400):
                dp[i][j][k] = min(dp[i - 1][j][k], dp[i][j][k])
                if j + a < 400 and k + b < 400:
                    dp[i][j + a][k + b] = min(dp[i][j + a][k + b], dp[i - 1][j][k] + c)

    ans = inf
    for j in range(1, 400):
        for k in range(1, 400):
            if j * wariai_b == k * wariai_a:
                ans = min(ans, dp[num][j][k])

    if ans == inf:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 96732
n = int(input())
dam = list(map(int,input().split()))
mountain =[0]*n
all_water = sum(dam)
def dam_water(num):
  sum_dam = 0
  for i in range(num,n,2):
    sum_dam += dam[i]
  return sum_dam

mountain[0] = all_water - 2 * (dam_water(1))

for i in range(1,n):
  mountain[i] = 2*dam[i-1] - mountain[i-1]

print(" ".join(map(str,mountain)))

Measured memory_bytes: 19096
#include <iostream>
#include <string>
#include <cmath>
using namespace std;

// int main(){
//   int N;
//   int large;
//   int counter, high_count;
//   int target;
//   cin >> N;
//   high_count = 0;
//   target = 1;
//   for(int i=1;i<N+1;i++){
//     int aNumber = i;
//     counter = 0;
//     while(aNumber%2 == 0) aNumber /=2, counter++;
//     if(counter> high_count){
//       target=i;
//       high_count = counter;
//     }
//   }

//   cout << target << endl;
// }

int main(){
  int N;
  int target;
  cin >> N;
  for(int i=6; i>=0;i--){
    if(N >= std::pow(2,i)){
      cout << std::pow(2,i) << endl;
      break;
    }
  }
}


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

int main() {  
 vector<int> arr;
 int s; cin >> s;
 arr.push_back(s);
	
  int previous = s;
  bool frag = true;
  while(frag) {
    int current;
    if(previous % 2 == 0) {
  		current = previous / 2;    
    } else {
    	current = previous * 3 + 1;
    }
    for(int i = 0; i < arr.size(); i++) {
      if(arr.at(i) == current) {
        frag = false;
        break;
      }
    }
    arr.push_back(current);
    previous = current;
  }
  cout << arr.size() << endl;

 return 0; 
}

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

int main(){
    int N,M;cin>>N>>M;
    priority_queue<ll> price;
    for(int i=0,p;i<N;i++){
        cin>>p;
        price.push(p);
    }
    for(int i=0,t;i<M;i++){
        t=price.top();
        price.push(t/2);
        price.pop();
    }
    ll ans=0;
    for(int i=0;i<N;i++){
        ans+=price.top();
        price.pop();
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1528