akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<deque>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const ll mod=1e9+7;
int n,m;
int x[N];
struct mat{
    ll a[3][3];
    mat(){memset(a,0,sizeof a);}
}A,C,e;
void debug(mat x){
    for(int i=0;i<3;i++,puts(""))
        for(int j=0;j<3;j++)
            printf("%d ",x.a[i][j]);
    puts("");
}
mat operator *(mat x,mat y){
    mat z;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            for(int k=0;k<3;k++){
                z.a[i][j]+=x.a[i][k]*y.a[k][j];
                z.a[i][j]%=mod;
            }
    return z;
}
mat operator ^(mat x,int y){
    mat res=e;
    while(y){
        if(y&1)
            res=res*x;
        //debug(x);
        x=x*x;
        //debug(res);
        //debug(x);
        y>>=1;
    }
    return res;
}
ll f[3],g[3];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d",&x[i]);
    A.a[0][0]=1,A.a[0][1]=2,A.a[0][2]=1;
    A.a[1][0]=0,A.a[1][1]=1,A.a[1][2]=1;
    A.a[2][0]=0,A.a[2][1]=0,A.a[2][2]=1;
    C.a[0][0]=2,C.a[0][1]=2,C.a[0][2]=1;
    C.a[1][0]=1,C.a[1][1]=1,C.a[1][2]=1;
    C.a[2][0]=1,C.a[2][1]=0,C.a[2][2]=1;
    e.a[0][0]=1,e.a[0][1]=0,e.a[0][2]=0;
    e.a[1][0]=0,e.a[1][1]=1,e.a[1][2]=0;
    e.a[2][0]=0,e.a[2][1]=0,e.a[2][2]=1;
    f[0]=1;
    x[++m]=n;
    for(int t=1,pos=0;t<=m;t++){
        int k=x[t]-pos-1;
        mat z=C^k;
        z=z*A;
        for(int i=0;i<3;i++){
            g[i]=0;
            for(int j=0;j<3;j++)
                g[i]=(g[i]+f[j]*z.a[j][i]%mod)%mod;
        }
        for(int i=0;i<3;i++)
            f[i]=g[i];
        pos=x[t];
    }
    printf("%lld\n",f[2]);
}


Measured memory_bytes: 512
N = int(input())
ahoge = input().split()
bhoge = input().split()
a = []
b = []
for i in range(N):
  a.append(int(ahoge[i]))
  b.append(int(bhoge[i]))

a.append(int(ahoge[N]))
count = 0

for i in range(N-1,-1,-1):
  hoge = b[i] - a[i+1]
  if hoge > 0:
    count += a[i+1]
    huga = hoge - a[i]
    if huga > 0:
      count += a[i]
      a[i] = 0
    else:
      count += hoge
      a[i] = a[i] - hoge
  else:
    count += b[i]

print(count)

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

typedef long long ll;
typedef unsigned long long ull;

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

  const ll mod = 998244353;

  vector<ll> d(n, 0);
  for (ll i = 0; i < n; ++i) {
    cin >> d[i];
  }
  if (d[0] != 0) {
    cout << 0 << endl;
    return 0;
  }
  sort(d.begin(), d.end());

  if (d.size() == 1 || d[1] == 0) {
    cout << 0 << endl;
    return 0;
  }

  ll ans = 1;
  ll x = 1;
  ll nodeCount = 1;
  for (ll i = 1; i < n; ++i) {
    if (d[i-1] < d[i]) {
      if (d[i] - d[i-1] > 1) {
        cout << 0 << endl;
        return 0;
      }
      x = nodeCount;
      nodeCount = 1;
    } else {
      nodeCount++;
    }
    ans = (ans*x)%mod;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.Linq;

namespace c
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = long.Parse(Console.ReadLine());
            var a = Console.ReadLine().Split().Select(i => long.Parse(i)).ToArray();
            var b = Console.ReadLine().Split().Select(i => long.Parse(i)).ToArray();

            long count = 0;
            for(var i = 0; i < n; i++){
                if(a[i] >= b[i]){
                    count += b[i];
                }else{
                    count += a[i];
                    b[i] = Math.Max(b[i] - a[i], 0);
                    if(a[i + 1] >= b[i]){
                        count += b[i];
                        a[i + 1] = Math.Max(a[i + 1] - b[i], 0);
                    }else{
                        count += a[i + 1];
                        a[i + 1] = Math.Max(a[i + 1] - b[i], 0);
                    }
                }
            }

            Console.WriteLine(count);
        }
    }
}


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

int v, e, s, t, u;
bool nc = 0;
long long d[100][100];
const long long Mx = 0xFFFFFFFF;

int main()
{
	cin >> v >> e;

	for (int i = 0; i < v; i++) {
		for (int j = 0; j < v; j++) {
			if (i == j)
				d[i][j] = 0;
			else
				d[i][j] = Mx;
		}
	}

	for (int i = 0; i < e; i++) {
		cin >> s >> t >> u;
		d[s][t] = u;
	}

	for (int i = 0; i < v; i++) {
		for (int j = 0; j < v; j++) {
			for (int k = 0; k < v; k++) {
				if(d[j][i] != Mx && d[i][k] != Mx)
					d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
			}
		}
	}

	for (int i = 0; i < v; i++) {
		if (d[i][i] < 0) {
			nc = 1;
			break;
		}
	}

	if (nc)
		cout << "NEGATIVE CYCLE" << endl;
	else {
		for (int i = 0; i < v; i++) {
			for (int j = 0; j < v - 1; j++) {
				if (d[i][j] == Mx)
					cout << "INF" << " ";
				else
					cout << d[i][j] << " ";
			}
			if (d[i][v - 1] == Mx)
				cout << "INF" << endl;
			else
				cout << d[i][v - 1] << endl;
		}
	}

	return 0;
}


Measured memory_bytes: 3172
#include <map>
#include <list>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
int n,a[105];
int A,B;
int main()
{
	fast;
	cin>>n;
	for (int i=1;i<=n;i++)
	   cin>>a[i];
	sort(a+1,a+n+1); 
	for (int i=1;i<=n;i++)
	   if (i%2!=0)
	      A+=a[i];
	   else
	      B+=a[i];
	cout<<abs(A-B);
	return 0;
}

Measured memory_bytes: 256
import sys
input=sys.stdin.readline

s=int(input())

#0<= x,y <=10**9
#s/2

if s<=10**9:
    print(0,0,1,0,0,s)
    exit()

y=(-1*s//(10**9))*(-1)
x=10**9*y-s

print(0,0,10**9,1,x,y)




Measured memory_bytes: 38384
#include <iostream>
using namespace std;
int main(){

  string c;
  cin >> c;
  if (c=="hi"||c=="hihi"||c=="hihihi"||c=="hihihihi"||c=="hihihihihi"){
    cout <<"Yes" <<endl;
  } else {
    cout <<"No" <<endl;
  }

return 0;



}

Measured memory_bytes: 256
#include<iostream>
#define MAX_L 1000000
#define MAX_SQRT 1000000
using namespace std;
typedef long long ll;
ll a,b;
bool is_prime[MAX_L],is_prime_small[MAX_SQRT];

void segment_sieve(ll a,ll b)
{
	for(int i=0;(ll)i*i<b;i++) is_prime_small[i]=true;
	for(int i=0;i<=b-a;i++)     is_prime[i]=true;

	for(int i=2;(ll)i*i<=b;i++)
	{
		if(is_prime_small[i])
		{
			for(int j=2*i;(ll)j*j<b;j+=i) is_prime_small[j]=false;
			for(ll j=(a+i-1)/i*i;j<=b;j+=i) is_prime[j-a]=false;
		}
	}
}

int main()
{
	//cin>>a>>b;
	while(cin>>a)
	{
		if(a==0) break;
		b=2*a;
		segment_sieve(a,b);
		ll res=0;
		for(int i=0;i<=b-a;i++)
		{
			if(i==0&&is_prime[i]) continue;
			if(is_prime[i]) res++;//cout<<i+a<<" ";
		}
		cout<<res<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
#include <tuple>

//#include <set>
//#include <unordered_map>
#include <stack>

using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)

#define max_n 100

int N;
string S;
vector<pair<int, int>> A[15];

int main() {

	cin >> N;
	vector<int> P, Q, A;

	rep(i, N) {
		int p;
		cin >> p;
		P.push_back(p - 1);
	}
	rep(i, N) {
		int p;
		cin >> p;
		Q.push_back(p - 1);
	}
	rep(i, N) {
		A.push_back(i);
	}

	int Ppos = -1;
	int Qpos = -1;
	int count = 1;
	do {
		bool Qsame = true;
		bool Psame = true;
		rep(i,N){
			if (A[i] != Q[i])Qsame = false;
			if (A[i] != P[i])Psame = false;
		}
		if (Qsame)Qpos = count;
		if (Psame)Ppos = count;
		if (Qpos >= 0 && Ppos >= 0)break;
		count++;
	} while (next_permutation(A.begin(), A.end()));     // 次の順列を生成

	cout << abs(Qpos-Ppos) << endl;
	return 0;
}


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


int main() {
  int n;
  cin >> n;
  //int d[n];
  vector<int> d;
  int cnt = 0;
  int a;
  for (int i = 0; i < n; i++) {
    cin >> a;
    d.push_back(a);
  }
  //mergeSort(d, n, 0, n);
  sort(d.begin(), d.end());


  int mid = -1 + (d.size() / 2) ;
  cnt = d[mid + 1] - d[mid];
  cout << cnt << endl;

  return 0;
}


Measured memory_bytes: 892
import sys
input = sys.stdin.readline
import itertools

n = int(input())
*p, = map(int, input().split())
*q, = map(int, input().split())

l = list(range(1, n+1))
l = list(itertools.permutations(l))
a = l.index(tuple(p))
b = l.index(tuple(q))

print(abs(a-b))

Measured memory_bytes: 8052
import sys
input = sys.stdin.readline



def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    ans = 0
    for a in A:
        while not a & 1:
            a = a // 2
            ans += 1

    print(ans)


    
    

if __name__ == '__main__':
    main()




Measured memory_bytes: 4084
#!python3

# input
S = input()


def main():
    n = len(S)
    p = [None] * n
    p[0] = 1
    for i in range(1, n):
        p[i] = (p[i - 1] * 10) % 2019
    
    d = {i: 0 for i in range(2019)}
    d[0] = 1
    ans = 0
    x = 0
    for i in range(n):
        x = (x + int(S[n - i - 1]) * p[i]) % 2019
        ans += d[x]
        d[x] += 1
    
    print(ans)


if __name__ == "__main__":
    main()


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

BL=[[0]*10 for i in range(10)]

for i in range(1,N+1):
    BL[int(str(i)[0])][int(str(i)[-1])]+=1

ANS=0
for i in range(10):
    for j in range(10):
        ANS+=BL[i][j]*BL[j][i]

print(ANS)

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

int main() {
  int h, w;
  cin >> h >> w;
  vector<vector<char>> masu(h, vector<char>(w));
  for(int i = 0; i < h; i++){
	for(int j = 0; j < w; j++){
      cin >> masu.at(i).at(j);
    }
  }
  vector<int>height(h);
  vector<int>width(w);
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
	  if(masu.at(i).at(j) == '#'){
        break;
      }else if(j == w-1){
        height.at(i) = 1;
      }
    }
  }
  for(int j = 0; j < w; j++){
	for(int i = 0; i < h; i++){
      if(masu.at(i).at(j) == '#'){
        break;
      }else if(i == h-1){
        width.at(j) = 1;
      }
    }
  }
    
  int end = w - 1;
  for(int j = w-1; j >= 0; j--){
	if(width.at(j) == 1){
	  end--;
    }else{
	  break;
    }
  }
  for(int i = 0; i < h; i++){
    if(height.at(i) == 1){
      	continue;
    }
    for(int j = 0; j < w; j++){
	  if(width.at(j) == 1){
		continue;
      }
      cout << masu.at(i).at(j);
      if(j == end){
        cout << endl;
      }
    }
  }/*
  for(int i = 0; i < h; i++){
	cout << height.at(i);
    if(i == h-1){
      cout << endl;
    }
    else{
      cout << " ";
    }
  }
  for(int j = 0; j < w; j++){
	cout << width.at(j);
    if(j == w-1){
	  cout << endl;
    }
  }
  cout << end << endl;*/
}

Measured memory_bytes: 256
package main
import (
    "fmt"
)

func main() {
    var k int
    var x int
    fmt.Scan(&k)
    fmt.Scan(&x)

    min := x - (k-1)
    max := x + (k-1)
    
    if min < -1000000 {
        min = -1000000
    }

    if max > 1000000 {
        max = 1000000
    }

    for i := min; i <= max; i++ {
        fmt.Printf("%d ", i);;
    }
}


Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
#include<utility>

using namespace std;

typedef long long int64;

int main(void){
    int64 N;
    cin>>N;
    int64 ans=0;
    vector<int64> A(N+1);
    vector<int64> B(N);
    for(int64 i=0;i<N+1;i++){
        cin>>A[i];
    }
    for(int64 i=0;i<N;i++){
        cin>>B[i];
    }

    for(int64 i=0;i<N;i++){
        if(B[i]>=A[i]){
            ans+=A[i];
            B[i]-=A[i];
            A[i]=0;
            if(B[i]>=A[i+1]){
                ans+=A[i+1];
                B[i]-=A[i+1];
                A[i+1]=0;
            }else{
                ans+=B[i];
                A[i+1]-=B[i];
                B[i]=0;
            }
        }else{
            ans+=B[i];
            A[i]-=B[i];
            B[i]=0;
        }
    }

    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 1792
// Problem: C - Iroha's Obsession
// Contest: AtCoder - AtCoder Regular Contest 058
// URL: https://atcoder.jp/contests/arc058/tasks/arc058_a
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 1;

string n;
int k;
int d[11];

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> k;
  for (int i = 1; i <= k; i++) {
    cin >> d[i];
  }
  vector<char> v;
  for (int i = 0; i < 10; i++) {
    if (!binary_search(d + 1, d + k + 1, i)) {
      v.push_back(i + '0');
    }
  }
  int ans = INT_MAX;
  for (auto& d1 : v) {
    for (auto& d2 : v) {
      for (auto& d3 : v) {
        for (auto& d4 : v) {
          for (auto& d5 : v) {
            string c = "";
            c += d1, c += d2, c += d3, c += d4, c += d5;
            c.resize(n.size() + 1);
            int a = stoi(c), b = stoi(n);
            if (a >= b) ans = min(ans, a);
            c.resize(n.size());
            a = stoi(c);
            if (a >= b) ans = min(ans, a);
          }
        }
      }
    }
  }
  cout << ans;
}

Measured memory_bytes: 3616
N = int(input())
X = list(map(lambda x: int(x), input().split(' ')))

afters = [0 for _ in range(N)]
after_x_dict = {}
for after, (before, x) in enumerate(sorted(list(enumerate(X)), key=lambda x:x[1])):
    afters[before] = after
    after_x_dict[after] = x

threshold = N//2 - 1
for i in range(N):
    if  afters[i] <= threshold:
        print(after_x_dict[threshold+1])
    else:
        print(after_x_dict[threshold])


Measured memory_bytes: 121484
#include<iostream>
#include<string>
#include<algorithm>
#include <stdio.h>
#include<iostream>
#include<iomanip>
#include<cmath>
#include<array>
#include<vector>
#include<set>
#include <utility>
#include <map>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
#include <iostream>
using namespace std;

/* 入力 */

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

  int a[110000],b[110000];
  for(int i=0; i<n ; i++)
  cin>>a[i]>>b[i];

  sort(a,a+n);
  sort(b,b+n);
  int cnt=0;
  for(int i=n-1;b[i]>=a[n-1];i--){
    h-=b[i];
    cnt++;
    if(h<=0){cout<<cnt<<endl; return 0;}
  }

  cout<<cnt+(h+a[n-1]-1)/a[n-1]<<endl;
}


Measured memory_bytes: 1024
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

const LL mod = 1000000007;
LL N, X;
std::vector<LL>S;
std::vector<std::vector<LL>>memo;

LL dp(LL i, LL j)
{
	if (j == N) return i;
	if (memo[i][j] != -1) return memo[i][j];
	LL res1 = dp(i%S[j], j + 1);
	LL res2 = (dp(i, j + 1)*(N - j - 1)) % mod;
	return memo[i][j] = (res1 + res2) % mod;
}

int main()
{
	in >> N >> X;
	S.resize(N);
	rep(i, N) in >> S[i];

	memo.resize(X + 1, std::vector<LL>(N + 1, -1));
	std::sort(S.begin(), S.end(), std::greater<LL>());
	out << dp(X, 0) << std::endl;
}


Measured memory_bytes: 160384
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define F first
#define S second
#define pi acos(-1)
using ll = long long;
using namespace std;
using namespace __gnu_pbds;
using vl = vector<ll>;
using pll =  pair<ll,ll>;
const ll mod = 1000000007;
const ll infi = 1000000000000000;
const ll md = 998244353;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;


ll power(ll x,ll y){
    ll res = 1;
    while(y){
        if(y&1)
            res = (res*x)%md;
        x = (x*x)%md;
        y = y/2;
    }
    return res;
}

void solve(){
    int n;
    cin>>n;
    vl a(n);
    ll ans=0;
    set<int> s;
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(i%2 == 0)
            s.insert(a[i]);
    }

    sort(a.begin(), a.end());

    for(int i=0;i<n;i++){
        if(i%2 == 0)
            s.erase(a[i]);
    }

    cout<<s.size();
}
 
int main()
{
    
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //int n; cin>>n; for (int i = 0; i < n; ++i)
    solve();
    return 0;
}


Measured memory_bytes: 3328
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <math.h>

using namespace std;

int main()
{
    int x;
    cin >> x;
    int c = 0;
    c += (x/500)*1000;
    c += ((x%500)/5)*5;
    cout << c << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
int main()
{
	long long int a, b;
	cin >> a >> b;
	long long int k = 1;
	long long int y;
	y = __gcd(a, b);
	for(long long int i = 2; y >= i*i;i++)
	{
		int x = 0;
		while (1)
		{
			if (y % i == 0)
			{
				if (x == 0)
				{
					k++;
					x = 1;
				}
				y = y / i;
				}
			else
			{
				break;
			}
		}
	}
	if (y != 1)
	{
		k++;
	}
	cout << k << endl;
	return 0;
}

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

using namespace std;


int main() {
  long long S;
  const long long x1 = 1e9, x2 = 1;

  cin >> S;
  long long y2 = S / x1 + (S % x1 != 0 ? 1 : 0); 
  long long y1 = x1 * y2 - S;
  printf("0 0 %lld %lld %lld %lld\n", x1, y1, x2, y2);

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
 
 
int main(){
  int w;
  while(true){
    cin >> w;
    if(w == -1)break;
    int sum = 0,pre = 4280;
    sum += 1150;
    if(w >= 10 && w <= 20)sum += (w-10)*125;
    else if(w >= 20)sum += 10*125;
    if(w >= 20 && w <= 30)sum += (w-20)*140;
    else if(w >= 30)sum += 10*140;
    if(w >= 30)sum += (w-30)*160;
    cout << pre - sum << endl;
  }
  return 0;
}


Measured memory_bytes: 3088
use std::cmp::*;
use std::collections::*;
use std::io::*;
use std::str::*;
use std::string::*;
use std::f64::consts::PI;

struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        Self(r, std::io::BufWriter::new(w))
    }

    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.to_string().as_bytes()).unwrap();
    }

    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let s: String = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect();

        return s.parse::<T>().ok().unwrap();
    }

    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

fn prime_factorization(n: i64) -> HashMap<i64, i64> {
    let mut n = n;
    let mut res = HashMap::new();
    let mut i = 2;
    while i * i <= n {
        while n % i == 0 {
            n /= i;
            let count = res.entry(i).or_insert(0);
            *count += 1;
        }
        i += 1;
    }

    if n > 1 {
        res.insert(n, 1);
    }

    return res;
}

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let mut a: f64 = sc.read();
    let mut b: f64 = sc.read();
    let mut h: f64 = sc.read();
    let mut m: f64 = sc.read();

    let rad = PI * 2.0 * (
        h / 12.0 + (m / 60.0) / 12.0 - m / 60.0
    );

    let c2 = a * a + b * b - 2f64 * a * b * rad.cos();
    println!("{}", c2.sqrt());
}

Measured memory_bytes: 2964
#include <bits/stdc++.h>
using namespace std;
#define watch(x) cout << (#x) << " is " << (x) << '\n'
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef double db;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a; }
//head

void solve(){
    int a[3][3];
    for (int i = 0; i < 3; i++){
        for (int j = 0; j < 3; j++) cin >> a[i][j];
    }

    int n;
    cin >> n;
    vector<int> b(n);
    for (int i = 0; i < n; i++) cin >> b[i];

    bool marked[3][3] = {{false}};

    for (int i = 0; i < n; i++){
        for (int j = 0; j < 3; j++){
            for (int k = 0; k < 3; k++){
                if (a[j][k] == b[i]) marked[j][k] = true;
            }
        }
    }

    bool flag = false;
    int s = 0;
    for (int i = 0; i < 3; i++){
        s = 0;
        for (int j = 0; j < 3; j++){
            s += marked[i][j];
        }
        flag = flag || (s == 3);
    }

    for (int i = 0; i < 3; i++){
        s = 0;
        for (int j = 0; j < 3; j++){
            s += marked[j][i];
        }
        flag = flag || (s == 3);
    }
    s = 0;
    for (int i = 0; i < 3; i++){
        s += marked[i][i];
    }
    flag = flag || s == 3;

    s = 0;
    for (int i = 0; i < 3; i++){
        s += marked[i][3-i-1];
    }
    flag = flag || s == 3;

    string ans;
    if (flag) ans = "Yes\n";
    else ans = "No\n";
    cout << ans;
}

int main(void){ 
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    //int t; cin >> t; while (t--)
        solve();
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define myPair pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define qmax priority_queue<int>
#define qmin priority_queue<int,vector<int>,greater<int>>
#define all(x) x.begin(),x.end()
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define FORR(i,a,b) for(int i = a; i >= b; i--)

const int mxn = 1010, mod  = 1e9 + 7;
int dp[mxn][mxn];
bool c[mxn][mxn];
string s[mxn];
int R, C;

int f(int i,int j)
{
	if(c[i][j])
		return dp[i][j];
	if(i == R)
		dp[i][j] = f(i, j + 1);
	else if(j == C)
		dp[i][j] = f(i + 1, j);
	else
		dp[i][j] = (f(i, j + 1) + f(i + 1, j)) % mod;
	c[i][j] = 1;
	return dp[i][j];
}

int32_t main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> R >> C;
	FOR(i,1,R)
		cin >> s[i];

	memset(c,0,sizeof(c));
	FOR(i,1,R)
	{
		FOR(j,0,C - 1)
		{
			if(s[i][j] == '#')
			{
				dp[i][j + 1] = 0;
				c[i][j + 1] = 1;
			}
		}
	}
	dp[R][C] = 1;
	c[R][C] = 1;

	cout << f(1,1);
	return 0;
}

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

bool c[26];
int s[26];

int main()
{
//	freopen("c.txt","r",stdin);
	
	int len,n;
	char a[51];
	vector<bool> each;
	vector<int> se;
	bool check=false;

	scanf("%d",&n);
	
	for(int i = 0;i < n;i++)
	{
		each.assign(26,false);
		se.assign(26,0);
		
		scanf("%s",a);
		
		len = strlen(a);
		
		for(int j = 0;j < len;j++)
		{
			each[a[j]-'a'] = true;
			se[a[j]-'a']++;
		}
		for(int j = 0;j < 26;j++)
		{
			if(i>0 && c[j] && !each[j]) c[j] = false;
			else if(i==0 && each[j]) c[j] = true;
			if(i==0) s[j] = se[j];
			else if(i>0) s[j] = min(s[j],se[j]);
		}
	}
	for(int i = 0;i < 26;i++)
	{
		if(c[i])
		{
			check = true;
			for(int j = 0;j < s[i];j++) 
				printf("%c",'a'+i);
		}
	}
	//if(!check)
}
			 
	
			

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

bool searchEdge(const int a[][2], int n, int edge[]);
int calcArea(const int a[][2], const int edge[]);

int main(void)
{
	int a[20001][2];
	a[0][0] = 0;

	char ch;
	int cnt = 0;
	while (cin >> ch) {
		if (ch == '\\') a[cnt][1] = a[cnt][0] - 1;
		else if (ch == '/') a[cnt][1] = a[cnt][0] + 1;
		else if (ch == '_') a[cnt][1] = a[cnt][0];
		else break;
		a[cnt + 1][0] = a[cnt][1];
		cnt++;
	}

	int edge[2];
	edge[1] = -1;
	int area[10000];
	int k = 0;
	while (1) {
		if (searchEdge(a, cnt, edge)) {
			area[k] = calcArea(a, edge);
			k++;
		}
		if (edge[1] >= cnt - 1) break;
	}

	int sum = 0;
	for (int i = 0; i < k; i++) {
		sum += area[i];
	}

	cout << sum << endl;
	cout << k;
	for (int i = 0; i < k; i++) {
		cout << " " << area[i];
	}
	cout << endl;

	return 0;
}

bool searchEdge(const int a[][2], int n, int edge[])
{
	edge[0] = edge[1] = edge[1] + 1;
	int i;
	for (i = edge[0]; i < n; i++) {
		if (a[i][1] - a[i][0] == -1) {
			edge[0] = i;
			break;
		}
	}
	if (i >= n) {
		edge[1] = n - 1;
		return false;
	}

	int height = a[edge[0]][0];
	edge[1] = edge[0];
	int j;
	for (j = edge[1]; j < n; j++) {
		if (a[j][1] == height) {
			edge[1] = j;
			break;
		}
	}
	if (j >= n) return false;

	return true;
}

int calcArea(const int a[][2], const int edge[])
{
	int max = a[edge[0]][0];
	double area = 0;
	for (int i = edge[0]; i <= edge[1]; i++) {
		area += (-(a[i][0] - max));
		area += (-(a[i][1] - a[i][0]) / 2.0);
	}

	return (int)area;
}

Measured memory_bytes: 3252
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac
import bisect
import sys
import logging
import heapq
logging.basicConfig(level=logging.DEBUG)

input = sys.stdin.readline

setrecursionlimit(1000000)

def main():
    N,K=[int(x) for x in input().split()]
    S=list(input())

    init=0
    for i in range(len(S)-1):
        if S[i]==S[i+1]: init+=1
    
    print(min(N-1, init+2*K))

main()

Measured memory_bytes: 78700
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	void io() {
		Scanner sc = new Scanner(System.in);
		
		while(true) {
			String src = sc.next();
			
			if( Integer.parseInt(src) == 0 ) break;
			
			solve(src);
		}
		
		sc.close();
	}
	
	void solve(String str) {
		int cnt = 0;
		while(true) {
			if( Integer.parseInt(str) == 6174 ) {
				System.out.println(cnt);
				break;
			}
			
			int len = str.length();
			char[] ss = str.toCharArray();
			char[] ls = new char[len];
			
			Arrays.sort(ss);
			for(int i = 0; i < len; ++i) {
				ls[i] = ss[len-1-i];
			}
			
			int l = Integer.parseInt(new String(ls));
			int s = Integer.parseInt(new String(ss));
			
			if( l == s ) {
				System.out.println("NA");
				break;
			}
			
			str = Integer.toString(l-s);
			while(str.length()<4) {
				str = "0" + str;
			}
			++cnt;
		}
	}
	
	public static void main(String[] args) {
		new Main().io();
	}
	
	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}
}

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

#define ll long long
#define ull unsigned long long

using namespace std;

int main() {
	ll N;
	cin >> N;

	vector <ll> ans(N, 0);
	for (int ii = 0; ii < N-1; ++ii){
		ll tmp = 0;
		cin >> tmp;
		tmp--;
		ans[tmp]++;
	}

	for (int ii = 0; ii < N; ++ii){
		cout << ans[ii] << endl;
	}


	return 0;
}


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

int d[4]={0};

int main(void){
	string s;
	cin >> s;
	int n=s.size();
	for(int i=0;i<n;i++){
		if(s[i]=='N') d[0]=1;
		if(s[i]=='W') d[1]=1;
		if(s[i]=='S') d[2]=-1;
		if(s[i]=='E') d[3]=-1;
	}
	
	if(d[0]+d[2]==0&&d[1]+d[3]==0) cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}


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

int main(){
    int n;
    cin >> n;
    int S[n+1];
    for (int i = 0; i < n; i++) cin >> S[i];
    int q;
    cin >> q;
    int cnt = 0;
    for (int i = 0; i < q; i++) {
        int T;
        cin >> T;
        S[n] = T;
        int j = 0;
        while (S[j] != T) j++;
        if (j != n) cnt++;
    }
    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 3060
#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    int a[n]; for (int i = 0; i < n; i++) cin >> a[i];
    int ub = 1 << 30, lb = 0;
    while (ub - lb > 1) {
        int mid = (ub + lb) / 2;
        vector<int> s(n+1);
        s[0] = n+1;
        for (int i = 1; i <= n; i++) s[i] = s[i-1] + (a[i-1] <= mid ? 1 : -1);
        long long sum = 0;
        vector<int> bit(2*n+2);
        for (int i = 0; i <= n; i++) {
            for (int j = s[i]-1; j > 0; j -= j&-j) sum += bit[j];
            for (int j = s[i]; j < bit.size(); j += j&-j) bit[j]++;
        }
        if ((long long)n * (1+n) / 4 < sum) ub = mid;
        else lb = mid;
    }
    cout << ub << endl;
}


Measured memory_bytes: 1808
#include <bits/stdc++.h>
#define range(i, l, r) for(int (i) = (l); (i) < (r); (i)++)
#define reversed_range(i, l, r) for (int (i) = (r) - 1; (i) >= l; (i)--)
using namespace std;
template <typename T>
using vec = vector<T>;
using lint = long long;
using ulint = unsigned long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;

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

template <typename T>
ostream& operator <<(ostream& os, vec<T> v) {
    os << "[";
    for (int i = 0; i < v.size() - 1; i++) {
        os << v.at(i) << ", ";
    }
    return os << v.at(v.size() - 1) << "]";
}

template <typename T>
ostream& operator <<(ostream& os, set<T>& s) {
    os << "{";
    if (s.begin() == s.end()) return os << "}";
    auto it_first_item = s.begin();
    cout << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        cout << ", " << *it;
    }
    return cout << "}";
}

template <typename T>
ostream& operator <<(ostream& os, unordered_set<T>& s) {
    os << "{";
    if (s.begin() == s.end()) return os << "}";
    auto it_first_item = s.begin();
    cout << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        cout << ", " << *it;
    }
    return cout << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, map<K, V> m) {
    os << "{";
    if (m.begin() == m.end()) return os << "}";
    auto it_first_item = m.begin();
    cout << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        cout << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, unordered_map<K, V> m) {
    os << "{";
    if (m.begin() == m.end()) return os << "}";
    auto it_first_item = m.begin();
    cout << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        cout << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

lint pow(lint num, lint e, lint MOD) {
    lint res = 1;
    lint cur_num = num;
    while (e) {
        if (e & 1) {
            res *= cur_num;
            res %= MOD;
        }
        cur_num *= cur_num;
        cur_num %= MOD;
        e >>= 1;
    }
    return res;
}

int main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    string s;
    cin >> s;
    string res;
    for (const char c : s) {
        if (c != 'B') res.push_back(c);
        else if (res.size() > 0) res.pop_back();
    }
    cout << res << "\n";
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int X = scanner.nextInt();
        int max = 1;
        for (int x = X / 2; x > 1; x--) {
            for (int y = X / 2; y > 1; y--) {
                double pow = Math.pow((double) x, (double) (y));
                if (pow > max && pow <= X) {
                    max = ((int) pow);
                }
            }
        }
        System.out.print(max);
    }
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
long long mo = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}
ld PI=3.14159265358979323846;

int main(){
    ll D;
    cin >> D;
    vector<ll> c(26);
    rep(i,26){
        cin >> c[i];
    }
    vector<vector<ll>> s(D,vector<ll>(26));
    rep(i,D){
        rep(j,26){
            cin >> s[i][j];
        }
    }
    vector<ll> t(D);
    rep(i,D){
        cin >> t[i];
        t[i]--;
    }
    vector<ll> memo(26,-1);
    ll score = 0;
    rep(i,D){
        score += s[i][t[i]];
        memo[t[i]] = i;
        rep(j,26){
            score -= (i-memo[j])*c[j];
        }
        cout << score << endl;
    }
}


Measured memory_bytes: 3664
#include "bits/stdc++.h"
using namespace std;

int n, a, b, c;

int solve(vector<int> val) {
	if (val.size() == 3) {
		sort(val.begin(), val.end());
		return abs(val[0]-c) + abs(val[1]-b) + abs(val[2]-a);
	}
	int best = INT_MAX;
	sort(val.begin(), val.end());
	for (int i=0; i<val.size(); i++) {
		for (int j=i+1; j<val.size(); j++) {
			for (int k=j+1; k<val.size(); k++) {
				best = min(best, abs(val[i]-c) + abs(val[j]-b) + abs(val[k]-a));
			}	
		}
	}
	for (int i=0; i<val.size(); i++) {
		for (int j=i+1; j<val.size(); j++) {
			vector<int> nv;
			nv.push_back(val[i]+val[j]);
			for (int x=0; x<val.size(); x++) {
				if (x == i || x == j) continue;
				nv.push_back(val[x]);
			}
			best = min(best, 10 + solve(nv));
		}
	}
	return best;
}

int main() {
 
	cin >> n >> a >> b >> c;
	vector<int> t(n);
	for (int i=0; i<n; i++) cin >> t[i];
	cout << solve(t);
	
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
  int N;
  cin >> N;

  int al[N];
  for (int i = 0; i < N; i++) {
    cin >> al[i];
  }

  int cost = 1e+9+1;
  for (int A = -100; A <= 100; A++) {
    int costSum = 0;
    for (int i=0; i<N; i++) {
      costSum += (al[i] - A) * (al[i] - A);
    }
    cost = min(cost, costSum);
  }
  cout << cost << endl;
  return 0;
}

Measured memory_bytes: 256
def resolve():
    A, B = list(map(int, input().split()))
    import math
    for i in range(1, math.ceil(100/0.08)+1):
        if math.floor(i*0.08) == A and math.floor(i*0.1) == B:
            print(i)
            return
    print(-1)


if '__main__' == __name__:
    resolve()

Measured memory_bytes: 63548
#include <stdio.h>

int main()
{
    int n, a[100];
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    for (int i = n - 1; i >= 0; i--)
    {
        printf("%d", a[i]);
        if (i != 0)
        {
            printf(" ");}
            else
            {
                break;
            }
        
    }
    printf("\n");
    return 0;
}



Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<(n);++i)
#define rep2(i,a,b) for (ll i=(a);i<(b);++i)
#define debug(x) cout << #x << '=' << x << endl
#define all(v) (v).begin(),(v).end()
const ll MOD=1e9+7;
//const ll MOD=998244353;
const ll INF=1e9;
const ll IINF=1e18;
const double EPS=1e-8;
const double pi=acos(-1);

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

vector<int> Zalgorithm(const string &s){
    int n=s.size();
    vector<int> z(n);
    z[0]=n;
    int i=1,j=0;
    while(i<n){
        while(i+j<n&&s[j]==s[i+j]) ++j;
        z[i]=j;
        if (j==0){++i; continue;}
        int k=1;
        while(i+k<n&&k+z[k]<j) z[i+k]=z[k],++k;
        i+=k,j-=k;
    }
    return z;
}

vector<int> LCP(const string &s,const string &t){
    vector<int> Z=Zalgorithm(t+s);
    for (int &i:Z) i=min(i,(int)t.size());
    return vector<int>(Z.begin()+t.size(),Z.end());
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; string S; cin >> N >> S;
    int ans=0;
    rep(i,N){
        string T=S.substr(i);
        vector<int> lcp=Zalgorithm(T);
        rep2(j,1,lcp.size()) chmax(ans,min((int)j,lcp[j]));
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include <functional>
#include<vector>
#include<math.h>
#include<bitset>
#include<string>
#include <deque>
#include<queue>
#include <iomanip>
#include<map>
#include <random>
#include<type_traits>
#include<stack>
#include <sstream> 
using namespace std;


#define ll long long int
#define all(v) begin(v), end(v)
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = (int)(s); i < (int)(n); i++)
//typedef vector<int> V;
//typedef vector<VV> VVV;

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
	vector.erase(vector.begin() + index);
}


int main() {
	int n,max=0,h,y=0;
	cin >>n;
	for (int i = 0; i < n; i++) {
		cin >> h;
		if (max <= h) {
			max = h;
			y += 1;
		}
	}
	cout << y << endl;
}


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

using namespace std;
const int nn = 2e5 + 5;
long long dp[nn][3], n, arr[nn];

long long rek(int idx, int bef) {
	if (idx == n) return 0;
	if (dp[idx][bef] == -1) {
		if (bef == 0) {
			if (idx == n - 1) dp[idx][bef] = rek(idx + 1, 0) + arr[idx];
			else dp[idx][bef] = max(rek(idx + 1, 0) + arr[idx], 
							   rek(idx + 1, 1) - arr[idx]);
		} else {
			if (idx == n - 1) dp[idx][bef] = rek(idx + 1, 0) - arr[idx];
			else dp[idx][bef] = max(rek(idx + 1, 0) - arr[idx], 
							   rek(idx + 1, 1) + arr[idx]);
		}
	}
	return dp[idx][bef];
}

int main() {
	memset(dp, -1, sizeof dp);
	scanf("%d", & n);
	for (int i = 0; i < n; i++) {
		scanf("%lld", & arr[i]);
	}	
	long long ans = rek(0, 0);
	printf("%lld\n", ans);
}

Measured memory_bytes: 10368
import java.util.*;
public class Main { 

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		while(true) {
			int N = stdIn.nextInt();
			if(N == 0) break;
			int[] I = new int[N+1];
			for(int i = 1; i <= N; i++) {
				I[i] = stdIn.nextInt();
			}
			int M = 256;
			int S = 99999999;
			int A = 99999999;
			int C = 99999999;
			double min = 99999999;
			for(int s = 0; s <= 15; s++) {
				for(int a = 0; a <= 15; a++) {
					for(int c = 0; c <= 15; c++) {
						int R[] = new int[N+1];
						R[0] = s;
						for(int i = 1; i <= N; i++) {
							R[i] = (a * R[i-1] + c)%M;
						}
						int O[] = new int[256];
						for(int i = 1; i <= N; i++) {
							O[(I[i] + R[i]) % M]++;
						}
						double H = 0;
						for(int i = 0; i < 256; i++) {
							if(O[i] > 0) {
								H -= O[i] / (double)N * Math.log(O[i] / (double)N);
							}
							
						}
						if(H + 1e-10 < min) {
							min = H;
							S = s;
							A = a;
							C = c;
						}
						
					}
				}
				
			}
			System.out.println(S + " " + A + " " + C);
		}
	}
}

	

Measured memory_bytes: 90180
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define int ll
#define double long double
#define nn '\n'
void YN(bool flg){cout<<(flg?"YES":"NO")<<'\n';}
void Yn(bool flg){cout<<(flg?"Yes":"No")<<'\n';}
void yn(bool flg){cout<<(flg?"yes":"no")<<'\n';}
#define SORT(a) sort(a.begin(),a.end())
#define REVERSE(a) reverse(a.begin(),a.end())
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define out(n) cout << n << '\n';
typedef vector<int> VI;
typedef vector<VI> VVI;
const int MOD = 1000000007;
const long long INF = 10e10;
const double PI = acos(-1.0);
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; }
template<class T>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }
int POW(int a, int n) { int r = 1; while (n > 0) { if (n & 1)r *= a; a *= a; n /= 2; }return r; }
int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*素因数分解*/map< int64_t, int >prime_factor(int64_t n){map< int64_t, int > ret;for(int64_t i = 2; i * i <= n; i++) {while(n % i == 0) {ret[i]++;n /= i;}}if(n != 1) ret[n] = 1;return ret;}
/*約数列挙*/vector<int> divisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------ライブラリとか----------------

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(15);

    double n; cin >> n;
    out((n-(int)n/2)/n);

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long n,a,b;
int x[100001];
int main(){
	long long s=0;
	cin>>n>>a>>b;
	cin>>x[1];
	for(int i=2;i<=n;i++)
	{
		cin>>x[i];
		long long m=a*(x[i]-x[i-1]);
		if(m>=b)s+=b;
		else s+=m;
	}
	cout<<s;
	return 0;
} 

Measured memory_bytes: 640
#include<iostream>

using namespace std;

int main()
{
	long long int H,sum=0;
	int N,A[100000];
	cin >> H;
	cin >> N;
	for(int i =0; i<N; i++)
    {
        cin >> A[i];
        sum=sum+A[i];
    }
    if(sum>=H)
        cout << "Yes";
    else
        cout << "No";
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <climits>
#include <cmath>
#include <map>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++ )
#define repf(i,m,n) for(int (i)=m;(i)<n;(i)++)
#define all(v) (v).begin(), (v).end()
#define ll long long
#define vec(name,num) vector<ll> name((num),0);
#define op(i) cout<<(i)<<endl;
#define ip(i) cin>>(i);
#define opN cout<<"No"<<endl;
#define opY cout<<"Yes"<<endl;
#define opP cout<<"Possible"<<endl;
#define opI cout<<"Impossible"<<endl;
#define mat(name,fnum,snum); vector<vector<ll>> name((fnum),vector<ll>((snum),0));
#define debugP int debug_point; cin>>debug_point;
template <typename T>
void putv(vector<T>& V){
	// cout << "The elements in the vector are: " << endl;
	for(auto x: V)
		cout << x << " ";
	cout << endl;
}
template <class T>
vector<T> getv(ll n){
	vector<T> Vector_temp;
	rep(i,n){
		T input;
		cin >> input;
		Vector_temp.emplace_back(input);
	}
	return Vector_temp;
}
ll gcd(ll c,ll b){
    while(1){
        if(c%b!=0){
        ll tmp=b;
        b=c%b;
        c=tmp;
        }else{
            return b;
        }
    }
}
/* <3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3*/

bool ss(string s){
    rep(i,s.size()/2){
        if(s[i]!=s[i+s.size()/2]){
            return false;
        }
    }
    return true;
}


int main(){
    string s;
    cin>>s;
    while(1){
        s.erase(s.size()-2,2);
        if(ss(s)){
            op(s.size());
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
S = input()
K = int(input())

pre_s = ""
ls = []
temp = 1
for s in S:
    if s == pre_s:
        temp += 1
    else:
        ls.append((pre_s,temp))
        temp = 1
    pre_s = s
ls.append((pre_s,temp))

if len(ls)==2:
    s,l = ls[1]
    print((l*K)//2)
    exit()
ans = 0
if S[0] != S[-1]:
    for s,l in ls[1:]:
        ans += l//2
    ans *= K
else:
    for s,l in ls[2:-1]:
        ans += l//2
    ans *= K
    s0,l0 = ls[1]
    s1,l1 = ls[-1]
    ans += l0//2
    ans += l1//2
    ans += (K-1)*((l0+l1)//2)
print(ans)





Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for (int i = 0; i< (n); ++i)
const int INF = 1001001001;
const int mod = 1000000007;
/*
 bit全探索 + DP
*/
int main() {

    int H, W, K;
    cin >> H >> W >> K;
    vector<vector<int> > dp(H + 1, vector<int>(W, 0)); dp[0][0] = 1;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {

            /* bit 全探索 */
            for (int k = 0; k < 1 << (W - 1); ++k) {
                // Check if two horizontal lines are connecting
                // 2 つの横線がつながっていないか調べる
                bool ok = true;
                for (int l = 0; l < W - 2; ++l) {
                    if (((k >> l) & 1) && ((k >> (l + 1)) & 1)) {
                        ok = false;
                    }
                }

                /* DP */
                if (ok) {
                    if (j >= 1 && ((k >> (j - 1)) & 1)) {
                        // The case which goes left
                        // 左方向に横線をたどるケース
                        dp[i + 1][j - 1] += dp[i][j];
                        dp[i + 1][j - 1] %= mod;
                    }
                    else if (j <= W - 2 && ((k >> j) & 1)) {
                        // The case which goes right
                        // 右方向に横線をたどるケース
                        dp[i + 1][j + 1] += dp[i][j];
                        dp[i + 1][j + 1] %= mod;
                    }
                    else {
                        // The case which goes straight
                        // 横線をたどらないケース
                        dp[i + 1][j] += dp[i][j];
                        dp[i + 1][j] %= mod;
                    }
                }
            }
        }
    }
    cout << dp[H][K - 1] << '\n';
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long a[200010];
long long b[200010];
int main(){
	int n,m;
	long long k;
	cin>>n>>m>>k;
	for(int i=0;i<n;i++){
		cin>>a[i];
		if(i>0)a[i]=a[i]+a[i-1];
	}
	for(int i=0;i<m;i++){
		cin>>b[i];
		if(i>0)b[i]=b[i]+b[i-1];
	}
	int mx=upper_bound(b,b+m,k)-b;
	for(int i=0;i<n;i++){
		if(a[i]>k)break;
		mx=max(mx,i+1+(int)(upper_bound(b,b+m,k-a[i])-b));
	}
	cout<<mx<<endl;
	return 0;
}

Measured memory_bytes: 6756
N = int(input())
A_list = [int(A) for A in input().split()]

step_sum = 0
height_front = A_list[0]
for idx in range(1, len(A_list)):
    A = A_list[idx]
    if A < height_front:
        step_sum += height_front - A
    else:
        height_front = A

print(step_sum)


Measured memory_bytes: 32256
import sys

input = sys.stdin.readline

def main():
    t = 'ATGC'
    ans = 0
    s = input()
    temp = 0
    for i in range(len(s)):
        temp = 0
        if s[i] in t:
            temp += 1
            for j in range(i+1, len(s)):
                if s[j] in t:
                    temp += 1
                else:
                    break
            ans = max(ans, temp)

    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
from sys import stdin
from collections import deque
def main():
    #入力
    readline=stdin.readline
    n,m=map(int,readline().split())
    G=[[] for _ in range(n+1)]
    for i in range(m):
        a,b=map(int,readline().split())
        G[a].append(b)
        G[b].append(a)

    ans=[0]*(n+1)
    flags=[False]*(n+1)
    flags[1]=True
    d=deque([1])
    while len(d)>0:
        now=d.popleft()
        v=now
        for u in G[v]:
            if flags[u]==False:
                flags[u]=True
                ans[u]=v
                d.append(u)

    print("Yes")
    for i in range(2,n+1):
        print(ans[i])
        
if __name__=="__main__":
    main()


Measured memory_bytes: 92256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int sx,sy,tx,ty,t1,t2;
	cin>>sx>>sy>>tx>>ty;
	t1=tx-sx;
	t2=ty-sy;
	sx=sy=0;
	for(int i=0;i<t2;i++)
		cout<<'U';
	for(int i=0;i<t1;i++)
		cout<<'R';
	for (int i = 0; i < t2; ++i)
	{
		cout<<'D';
	}
	for(int i=0;i<=t1;i++)
		cout<<'L';
	for(int i=0;i<=t2;i++)
		cout<<'U';
	for(int i=0;i<=t1;i++)
		cout<<'R';
	cout<<'D';
	cout<<'R';
	for (int i = 0; i <= t2; ++i)
	{
		cout<<'D';
	}
	for(int i=0;i<=t1;i++)
		cout<<'L';
	cout<<'U';
}

Measured memory_bytes: 256