akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr  4 20:49:19 2020

@author: naoki
"""

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

criteria = sum(A) / (4*M)
count = 0
for i in range(N):
    if A[i] >= criteria:
        count+=1

if count >= M:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 39888
//Copyright(c)2017 Mstdream
#include<bits/stdc++.h>
using namespace std;

inline void splay(int &v){
	v=0;char c=0;int p=1;
	while(c<'0' || c>'9'){if(c=='-')p=-1;c=getchar();}
	while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
	v*=p;
}
long long l[555];
int main(){
	//freopen("xxx.in","r",stdin);
	l[0]=2,l[1]=1;
	for(int i=2;i<=88;i++)l[i]=l[i-1]+l[i-2];
	int x;cin>>x;cout<<l[x]<<endl;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
A = list(map(int, input().split()))
total = 0
flag = 0
ans = []
for a in A:
    total += a
to = total / (4 * M)
sort_A = sorted(A)
length = len(sort_A)
for i in range(M):
    ans.append(sort_A[length - i - 1])
for ans_sub in ans:
    if ans_sub < to:
        flag += 1
        break
if flag == 0:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(long long)(n);i++)
#define all(a) a.begin(), a.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
const ll MOD=1e9+7;
const ll INF=1e18;
const int MAX=510000;
const double pi=acos(-1);
int dx[8] = {1,0,-1,0,1,1,-1,-1};
int dy[8] = {0,1,0,-1,-1,1,1,-1};
// int d[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false); 
  
  ll n;
  ll t;
  cin >> n >> t;
  ll a[n];
  rep(i,n) cin >> a[i];
  
  map<ll,ll>mp;
  ll ma=0;
  ll mi = 1e9;
  rep(i,n){
    mi=min(a[i],mi);
    ll d = a[i]-mi;
    mp[d]++;
    ma=max(d,ma);
  }
  cout << mp[ma] << endl;
  return 0;
}


Measured memory_bytes: 10656
#include <iostream>
#include <stack>
using namespace std;
int main(){
	stack<int> a;
	int n;
	while(cin>>n && n!=-1){
		if(n==0)a.push(0);
		while(n){
			a.push(n%4);
			n/=4;
		}
		while(a.empty() != true){
			cout<<a.top();
			a.pop();
		}
		cout<<endl;
	}
	return 0;
}

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

using namespace std;

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

  int n;
  cin >> n;

  vector<int64_t> l(n);
  for (int i = 0; i < n; ++i) {
    cin >> l[i];
  }
  sort(l.begin(), l.end());

  int ans = 0;
  for (int i = 0; i < n - 2; ++i) {
    for (int j = i + 1; j < n - 1; ++j) {
      if (l[i] == l[j]) {
        continue;
      }
      for (int k = j + 1; k < n; ++k) {
        if (l[j] != l[k] && l[i] + l[j] > l[k]) {
          ++ans;
        }
      }
    }
  }

  cout << ans << '\n';

  return 0;
}


Measured memory_bytes: 3656
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
/*Rating 1-399 : gray
Rating 400-799 : brown
Rating 800-1199 : green
Rating 1200-1599 : cyan
Rating 1600-1999 : blue
Rating 2000-2399 : yellow
Rating 2400-2799 : orange
Rating 2800-3199 : red
*/
using namespace std;
int main()
{  int a[1000];
   int N;
   while(scanf("%d",&N)==1)
     { for(int i=0;i<N;i++) scanf("%d",&a[i]);
       sort(a,a+N);
       int b[9];
       int i;
       memset(b,0,sizeof(b));
       for( i=0;i<N&&a[i]<=3199;i++)
         { //printf("a[i]=%d\n",a[i]);
		  if(a[i]>=2800) b[8]++;
           else if(a[i]>=2400) b[7]++;
           else if(a[i]>=2000) b[6]++;
           else if(a[i]>=1600) b[5]++;
           else if(a[i]>=1200) b[4]++;
           else if(a[i]>=800)  b[3]++;
           else if(a[i]>=400)  b[2]++;
           else b[1]++;
		 }
       int sum=0;
       if(i!=0){
       for(int j=1;j<=8;j++)
         { if(b[j]!=0) {
         	//printf("j=%d\n",j);
		    sum++;
		    }
		 }
		 printf("%d ",sum);
	   if(i!=N)
	     {  printf("%d\n",N-i+sum);
		 }
	   else printf("%d\n",sum);
       }
       else printf("%d %d\n",1,N);
       /*Rating 1-399 : gray
Rating 400-799 : brown
Rating 800-1199 : green
Rating 1200-1599 : cyan
Rating 1600-1999 : blue
Rating 2000-2399 : yellow
Rating 2400-2799 : orange
Rating 2800-3199 : red
*/
     }
}


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

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long a,b,c;
    cin>>a>>b>>c;
    int ans =0;
    if(a==b && b==c && c==a)
    {
        if(a%2==1 || b%2==1 || c%2==1)
        {
            cout<<"0"<<"\n";
            return 0;
        }
    }
    while(1)
    {
        if(a==b && b==c && c==a)
        {
            cout<<"-1";
            return 0;
        }
        else if((a%2==1) || (b%2==1) || (c%2==1))
        {
            cout<<ans<<"\n";
            return 0;
        }
        else
        {
            int aa,bb,cc;
            aa=a;
            bb=b;
            cc=c;
            a=(bb/2)+(cc/2);
            b=(aa/2)+(cc/2);
            c=(bb/2)+(aa/2);
        }
        ans++;
    }
}

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

int main() {

  string s;

  cin >> s;

  int count = 0;

  if (s.at(0) == '1') count++;
  if (s.at(1) == '1') count++;
  if (s.at(2) == '1') count++;

  cout << count << endl;

}


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

int main(void){
    char str1[1000], str2[1000];
    int i,diff = 0,ans,cnt1 = 0 ,cnt2 = 0;

    scanf("%s",str1);
    scanf("%s",str2);

    //str1のサイズ
   // str1[strlen(str1) + 1] = '\0';

    //str2のサイズ
  //  str2[strlen(str2)+ 1] = '\0';

    ans = strlen(str2); //答えは必ず 0　～　str2の長さ

    //全探索
    for(i = 0;i <= strlen(str1) - strlen(str2) ; i++)
    {
        diff = 0;
        for(int j = 0; j < strlen(str2);j++)
        {
            if(str2[j] != str1[j + i] )
                diff++;
        }

        if(ans > diff)
            ans = diff;
    }


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

    return 0;
    
}




Measured memory_bytes: 1732
use std::io::prelude::*;

fn input<T>() -> T
where
    T: std::str::FromStr,
{
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

fn main() {
    let n: usize = input();
    let a: Vec<Vec<i64>> = (0..2).map(|_| (0..n).map(|_| input()).collect()).collect();

    let mut s = vec![vec![0; n + 1]; 2];
    for i in 0..n {
        s[0][i + 1] = s[0][i] + a[0][i];
        s[1][i + 1] = s[1][i] + a[1][i];
    }

    let mut ans = 0;
    for i in 1..n + 1 {
        ans = std::cmp::max(ans, s[0][i] + s[1][n] - s[1][i - 1]);
    }
    println!("{}", ans);
}


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

int main()
{
  string s;
  bool flag = false;
  cin >> s;

  int f, l;

  for (int i = 0; i < s.size(); i++) {
    if (s[i] == 'A') {
      f = i;
      break;
    }
  }

  for (int i = s.size() - 1; i >= 0; i--) {
    if (s[i] == 'Z') {
      l = i;
      break;
    }
  }

  cout << l - f + 1 << endl;

  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define maxi 300005
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define ll long long
#define si(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define TRACE
#ifdef TRACE
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
#else
#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)
#endif
#define gc getchar
#define REP(i,j,n)               for( i=j;i<n;i++)
#define PER(i,j,n)               for( i=n-1;i>=j;i--)
ll mpow(ll a, ll n,ll mod){
	ll ret=1;ll b=a;
	while(n) {
		if(n&1)
			ret=(ret*b)%mod;
		b=(b*b)%mod;
		n>>=1;
	}
	return (ll)ret;
}
ll gcd(ll a, ll b)
{
    if (a == 0 || b == 0)
       return 0;
    if (a == b)
        return a;
    if (a > b)
        return gcd(a-b, b);
    return gcd(a, b-a);
}
inline void read(int &x){
	x=0;
	register char c=gc();
	for(;c<'0' || c>'9';c=gc());
	for(;c>='0' && c<='9';c=gc())
		x=(x<<3)+(x<<1)+(c-'0');
}
inline void write(int x){
	register char buffor[35];
	register int i=0;
	do{
		buffor[i++]=(x%10)+'0';
		x/=10;
	} while(x);
	i--;
	while(i>=0) putchar(buffor[i--]);
	putchar('\n');
}
inline int in() { int x; read(x); return x; }
void solve();
int dbg=1;
using namespace std;
int main(){
	int t=1;
	//read(t);
	for(int i=0;i<t;i++){
		//printf("Case #%d:\n",i);
		solve();
	}
	return 0;
}
void solve() {
	ll i,j,k,a,b,c,d,l;
	cin>>a>>b>>c>>d;
	i=b/c-(a-1)/c;
	j=b/d-(a-1)/d;
	k=gcd(c,d);
	k=c*d/k;
	l=b/k-(a-1)/k;
	cout<<b-a+1-(i+j-l)<<endl;
}



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

using namespace std;
typedef long long int ll;
const int N=105,M=100005;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(NULL);
	int i,j,n,k,w,v;
	ll dp[N][M],best;
	cin>>n>>k;
	dp[0][0]=0;
	for(i=1;i<=k;++i) dp[0][i]=0;
	for(i=1;i<=n;++i){
		dp[i][0]=0;
		cin>>w>>v;
		for(j=1;j<=k;++j){
			if(j<w) dp[i][j]=dp[i-1][j];
			else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v);
		}
	}
	best=dp[n][1];
	for(i=2;i<=k;++i) best=max(best,dp[n][i]);
	cout<<best;
}

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

namespace TOPSIC
{
    partial class Program
    {
        static void Main(string[] args)
        {
          string H = Console.ReadLine();
            string ans = "Yes";

            if (H.Length < 2)
            {
                ans = "No";
                Console.WriteLine(ans);
                return;
            }

            for (int i = 0; i < H.Length; i++)
            {
                if (i % 2 == 0)
                {
                    if (H[i] != 'h')
                    {
                        ans = "No";
                        break;
                    }
                }
                else
                {
                    if (H[i] != 'i')
                    {
                        ans = "No";
                        break;
                    }
                }
            }

            if (H[H.Length - 1] == 'h')
            {
                ans = "No";
            }
            
            Console.WriteLine(ans);

        }
    }
}


Measured memory_bytes: 11092
#include<stdio.h>
#define MAX 100000

int A[MAX], n;
/* ??????A[p???r]????????°???A[r]???????????§?°????????????? */
int partition(int p, int r){
	int x, i, j, t;
	x = A[r];
	i = p - 1;
	for(j=p;j<r;j++){
		if(A[j] <= x){
			i++;
			t = A[i]; A[i] = A[j]; A[j] = t;
		}
	}
	t = A[i+1]; A[i+1] = A[r]; A[r] = t;
	
	return i+1;
}

int main(){
	int i, q;

	scanf("%d",&n);
	for(i=0;i<n;i++) scanf("%d",&A[i]);

	q = partition(0, n - 1);

	for(i=0;i<n;i++){
		if(i) printf(" ");
		if(i == q) printf("[");
		printf("%d",A[i]);
		if(i == q) printf("]");
	}
	printf("\n");

	return 0;
}

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

int main(){
  int a, b, k;
  cin >> a >> b >> k;
  int count=0;
  int i=a+1;
  while (count!=k){
    i--;
    if (a%i==0 && b%i==0) count++;
  }
  cout << i << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

// using namespace __gnu_pbds;
using namespace std;

#define fbo find_by_order
#define ook order_of_key
#define fi first
#define se second
#define long long long
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// void initiate_random() { mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count()); }

// /mnt/c/Users/vince/Desktop/POST-IOI/Codeforces/Regular/670

int n;
int X[200003], Y[200003];

int dist(int a, int b)
{
	return abs(X[a]-X[b]) + abs(Y[a]-Y[b]);
}

int main()
{
	// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	// freopen("input.in", "r", stdin);

	scanf("%d", &n);
	for(int i = 0; i < n; i++)
		scanf("%d %d", &X[i], &Y[i]);

	vector<int> xpy;
	vector<int> xmy;

	for(int i = 0; i < n; i++)
	{
		xpy.push_back(X[i]+Y[i]);
		xmy.push_back(-X[i]+Y[i]);
	}
	sort(xpy.begin(), xpy.end());
	sort(xmy.begin(), xmy.end());

	printf("%d\n", max(xpy.back()-xpy[0], xmy.back()-xmy[0]));

}

Measured memory_bytes: 6648
#include<bits/stdc++.h>
using namespace std;
string S;
int c=0;
int main(){
  cin >> S;
  if(S[0]!='A'){
    cout << "WA" << endl;
    return 0;
  }
  for(int i=1;i<S.size();i++){
    if(S[i]<='Z'){
      if(i>=2 && i<=S.size()-2){
        if(S[i]=='C' && c==0) c++;
        else{
          cout << "WA" << endl;
          return 0;
        }
      }
      else{
        cout << "WA" << endl;
        return 0;
      }
    }
  }
  if(c==0){
    cout << "WA" << endl;
    return 0;
  }
  cout << "AC" << endl;
  return 0;
}


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

using namespace std;

int main()
{
	unsigned long long i,n;
	unsigned long long Bnum, Wnum;
	string s;

	cin >> s;
	n = s.length();

	Bnum = Wnum = 0;
	for (i = 0; i < n; i++) {
		if (s[i] == 'B') {
			Bnum++;
		}
		else {
			Wnum++;
		}
	}

	unsigned long long ans = 0, anscount = 0;
	for (i = 0; i < n; i++) {
		if (s[i] == 'W'){
			anscount++;
			ans += i - Wnum + anscount;
		}
	}

	cout << ans << endl;
}


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

int main() {
    string s;
    cin >> s;
    int counter = 0;
    if (s[0] == 'o') ++counter;
    if (s[1] == 'o') ++counter;
    if (s[2] == 'o') ++counter;
    int sum = 700+counter*100;
    cout << sum << endl;
    }

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <utility>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <cmath>
#include <functional>
#include <chrono>
#include <cstring>
#include <limits.h>

using namespace std;
typedef long long lint;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<lint> vl;
typedef pair<lint,lint> pll;

void solve(){

}

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


    int h1,m1, h2, m2,k;
    cin>>h1>>m1>>h2>>m2>>k;

    int p = 60-m1 + (h2-h1-1)*60 + m2;
    cout<<p-k;




}


Measured memory_bytes: 3640
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_multi<T: std::str::FromStr>() -> Vec<T> {
    let mut s = std::string::String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}


fn main() {
    //println!("Hello, world!");

    let n: i32 = read(); //i32
    //println!("{}", n);

    let mut vn: Vec<i32> = read_multi(); //i32
    //println!("{:?}", vn);

    let mut res: i32 = 0;
    for i in 0..n as usize {
        let mut r: i32 = 0;
        loop {
            if vn[i] % 2 == 0 {
                r += 1;
                vn[i] = vn[i] / 2;
            } else {
                break;
            }
        }
        res = res + r;
    }
    println!("{}", res);
}


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

int n, m=15000, mi;
double cx, cy, d, mx, p=1.0, x[55], y[55];
double f(double p, double q) {return p*p + q*q;}

int main() {
	int i;
	cin >> n;
	for(i=0; i<n; i++) {
		cin >> x[i] >> y[i];
		cx += x[i]; cy += y[i];
	}
	cx /= n; cy /= n;
	while(m--) {
		mx = f(cx - x[0], cy - y[0]);
		mi = 0;
		for(i=1; i<n; i++) {
			d = f(cx - x[i], cy - y[i]);
			if(d > mx) mx = d, mi = i;
		}
		cx += (x[mi] - cx) * p;
		cy += (y[mi] - cy) * p;
		p *= 0.999;
	}
	printf("%.9f", sqrt(mx));
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

const int maxn = 2e5 + 5;
typedef long long LL;

LL x[maxn], y[maxn];
int n;

pair<LL, LL> p[maxn];
LL suf[maxn];
int main(){
    cin >> n;
    LL Rmax = 0, Rmin = 1e9, Bmax = 0, Bmin = 1e9;
    for(int i = 1;i <= n;i++){
        scanf("%lld%lld", &x[i], &y[i]);
        if(x[i] > y[i])
            swap(x[i], y[i]);
        Rmax = max(Rmax, x[i]);
        Rmin = min(Rmin, x[i]);
        Bmax = max(Bmax, y[i]);
        Bmin = min(Bmin, y[i]);
        p[i].first = x[i];
        p[i].second = y[i];
    } 
    LL ans = 1LL * (Rmax - Rmin) * (Bmax - Bmin);
    sort(p + 1, p + 1 + n);
    LL ans1 = p[n].first - p[1].first;
    LL pre = p[1].second;
    LL pre1 = p[1].second;
    for(int i = 2;i <= n;i++){
        ans1 = min(ans1, max(p[n].first, pre) - min(pre1, p[i].first));
        pre = max(pre, p[i].second);
        pre1 = min(pre1, p[i].second);
    }
    ans = min(ans, ans1 * (max(Bmax, Rmax) - min(Rmin, Bmin)));
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 6528
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> d(n);
    for (auto& i : d) cin >> i;
    sort(d.begin(), d.end());
    cout << d[n / 2] - d[n / 2 - 1] << endl;
}

Measured memory_bytes: 640
#include<stdio.h>

int main(void)
{
    int n;
    int i;
    int each_digit[5] ;
    int ok =0;
    for ( i = 0 ; i < 5 ; i++ ) each_digit[i]=0;

    scanf("%d", &n);

    for(i = 0 ; i < 5 ; i++ )
    {
//        printf("n= %d \n",n);
        each_digit[i] = n;
        n = n / 10; 
    }

    for(i = 0 ; i < 5 ; i++ )
    {
 //       printf("n= %d \n",each_digit[i]);
        each_digit[i] = each_digit[i] % 10 ;
    }

    for(i = 0 ; i < 5 ; i++ )
    {
        if(each_digit[i] == 7)
        {
            ok =1;
        }
    }

    if(ok == 1 )    printf("Yes");
    else            printf("No");

    return 0;


}




Measured memory_bytes: 1728
#include <cstdio>
#include <cstring>
#include <cmath>
#include <climits>
#include <iostream>
#include <iomanip>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <algorithm>
#include <numeric>
#include <functional>

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define ALL(a) (a).begin(),(a).end()

using namespace std;
typedef long long ll;

struct edge { int s, t, d; };
int V, E, R;
const ll Inf = 1L << 56;

int main(int argc, char *argv[])
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> V >> E >> R;
  edge es[E];
  ll d[V];
  REP(i,V) d[i] = Inf;
  d[R] = 0;
  REP(i,E) cin >> es[i].s >> es[i].t >> es[i].d;
  while (true) {
    bool update = false;
    REP(i,E) {
      edge e = es[i];
      if (d[e.s] == Inf)
        continue;
      ll dd = d[e.s] + e.d;
      if (d[e.t] > dd) {
        d[e.t] = dd;
        update = true;
      }
    }

    if (!update)
      break;
  }

  REP(i,V) {
    if (d[i] == Inf) {
      cout << "INF\n";
    } else {
      cout << d[i] << '\n';
    }
  }
  cout << flush;
    
  return 0;
}

Measured memory_bytes: 7696
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    cin >> n;

    vector<int> taste(n);
    int sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> taste[i];
        sum += taste[i];
    }

    int res = 0;
    for (int i = 0; i < n; i++) {
        sum -= taste[i];
        res += taste[i] * sum;
    }

    cout << res << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Text;

namespace AtTest.C_Challenge
{
    class ABC_052
    {
        static void Main(string[] args)
        {
            Method(args);
            Console.ReadLine();
        }

        static void Method(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            if (n == 1)
            {
                Console.WriteLine(1);
                return;
            }
            var cnt = new int[n + 1];
            for (int i = 2; i <= n; i++)
            {
                int sub = i;
                while (sub > 1)
                {
                    for (int j = 2; j <= i; j++)
                    {
                        if (sub % j == 0)
                        {
                            sub /= j;
                            cnt[j]++;
                            break;
                        }
                    }
                }
            }
            long allPat = 1;
            long mask = 1000000007;
            for(int i = 2; i <= n; i++)
            {
                allPat *= (cnt[i] + 1);
                allPat %= mask;
            }


            Console.WriteLine(allPat);
        }
    }
}


Measured memory_bytes: 11092
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Convert;
using static System.Math;

class Program
{
    static void Main(string[] args)
    {
        var s = ReadLine();
        var key = "keyence";
        if (key == s) { WriteLine("YES");return; }
        for(var i = 1; i <= s.Length; i++)
        {
            for(var j = 0; j < s.Length; j++)
            {
                var sp = "";
                if (j == 0) sp = s.Substring(i);
                else if (j == s.Length - 1)
                    sp = s.Substring(s.Length - i);
                else if(j+i<s.Length)
                    sp = s.Substring(0, j) + s.Substring(j + i);
                if (sp == key)
                {
                    WriteLine("YES");return;
                }
            }
        }
        WriteLine("NO");
    }
    private const string ALFA = "abcdefghijklmnopqrstuvwxyz";
    private const int MOD = 1000000007;
}


Measured memory_bytes: 11092
def bubbleSort(a,n):
	cnt=0
	for i in range(n-1,0,-1):
		for j in range(i):
			if a[j]>a[j+1]:
				a[j],a[j+1]=a[j+1],a[j]
				cnt+=1
	return cnt	
	
n=int(input())
a=list(map(int,input().split()))
cnt=bubbleSort(a,n)
print(' '.join(map(str,a)))
print(cnt)



Measured memory_bytes: 5600
#include <stdio.h>

int dice[7] = {0};
typedef enum {
	S = 0,
	N,
	W,
	E
} cmd;

void rotation(cmd command) {
	int tmp;
	switch (command) {
	case S:
		tmp = dice[1];
		dice[1] = dice[5];
		dice[5] = dice[6];
		dice[6] = dice[2];
		dice[2] = tmp;
		break;
	case N:
		tmp = dice[1];
		dice[1] = dice[2];
		dice[2] = dice[6];
		dice[6] = dice[5];
		dice[5] = tmp;
		break;
	case W:
		tmp = dice[1];
		dice[1] = dice[3];
		dice[3] = dice[6];
		dice[6] = dice[4];
		dice[4] = tmp;
		break;
	case E:
		tmp = dice[1];
		dice[1] = dice[4];
		dice[4] = dice[6];
		dice[6] = dice[3];
		dice[3] = tmp;
	}
	return;
}
void toFront(int front) {

	if (front == dice[1]) {
		rotation(S);
	} else if(front == dice[2]) {
		;
	} else if (front == dice[3]) {
		rotation(E);
		rotation(N);
	} else if (front == dice[4]) {
		rotation(W);
		rotation(N);
	} else if (front == dice[5]) {
		rotation(S);
		rotation(S);
	} else {
		rotation(N);
	}
}

void search(int up, int front) {
	int i;
	
	toFront(front);
	for (i = 0; (i < 3) && (dice[1] != up); ++i) {
		rotation(W);
	}
	return ;
}

int main(void) {
	int n, i;
	int up, front;
	for (i = 1; i <= 6; ++i) {
		scanf("%d", &dice[i]);
	}

	scanf("%d", &n);
	for (i = 0; i < n; ++i) {
		scanf("%d %d", &up, &front);
		search(up, front);
		printf("%d\n", dice[3]);
	}
	
	return 0;
}

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

using namespace std;

int main() {
  long long N;
  cin >> N;
  int ans = 11;
  for (long long i = 1; i * i <= N; ++i)
    if (N % i == 0)
      ans = min(ans, (int)max(to_string(i).size(), to_string(N / i).size()));
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
import copy, sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
A = [int(i) for i in input().split()]
edge = [[] for i in range(n)]

grundy = [-1] * n

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

def dfs(v):
    if grundy[v] != -1: return grundy[v]
    mex = [0] * (len(edge[v]) + 1)
    for vv in edge[v]:
        if A[vv] < A[v]: 
            gg = dfs(vv)
            if gg <= len(edge[v]): mex[gg] = 1
    for i in range(len(edge[v])+1):
        if mex[i] == 0:
            grundy[v] = i
            return i


ans = []
for i in range(n):
    if dfs(i) != 0: ans.append(i+1)

print(*ans)


Measured memory_bytes: 78632
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
#define INF (1e9)
#define PI (acos(-1))

int main() {
	int l;
	cin >> l;
	double ans, side;

	side = l / 3.0;
	ans = side*side*side;

	cout << fixed << setprecision(12) << ans;
	return 0;
}

Measured memory_bytes: 3764
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second

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

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const double EPS = 1e-8;

template<typename T> T chmax(T& a, const T& b){return a = (a > b ? a : b);}
template<typename T> T chmin(T& a, const T& b){return a = (a < b ? a : b);}

namespace Doubling {
    using NODE_TYPE = int;
    using COST_TYPE = long long;
    // d[i][0]はあらかじめ計算しておく！
    void preCalc(vector<vector<NODE_TYPE>>& d) {
        int n = d.size();
        int m = d[0].size();
        REP(j, 1, m) rep(i, n) {
            d[i][j] = d[d[i][j-1]][j-1];
        }
    }
    // 頂点uからcostでいける頂点を求める
    NODE_TYPE getNode(NODE_TYPE u, COST_TYPE cost, const vector<vector<NODE_TYPE>>& d) {
        int n = d.size();
        int m = d[0].size();
        NODE_TYPE cur = u;
        repr(j, m) {
            if(cost&(COST_TYPE(1)<<j)) {
                cur = d[cur][j];
            }
        }
        return cur;
    }
    // 頂点uから頂点vまでのコストを求める(iはトポロジカルソート後のidx)
    COST_TYPE getCost(NODE_TYPE u, NODE_TYPE v, const vector<vector<NODE_TYPE>>& d) {
        if(u >= v) assert(false);
        int n = d.size();
        int m = d[0].size();
        int cur = u;
        COST_TYPE ret = 0;
        while(cur < v) {
            if(d[cur][0] >= v) {
                ret += 1;
                break;
            }
            int j = lower_bound(all(d[cur]), v) - d[cur].begin() - 1;
            cur = d[cur][j];
            ret+= COST_TYPE(1) << j;
        }
        return ret;
    }
};

int main(){
    ll n, k;
    cin >> n >> k;
    vi a(n);
    rep(i, n) cin >> a[i];
    rep(i, n) a[i]--;
    vector<vector<int>> d(n, vi(62));
    rep(i, n) d[i][0] = a[i];
    Doubling::preCalc(d);
    cout << Doubling::getNode(0, k, d) +1 << '\n';
    return 0;
}

Measured memory_bytes: 58700
#include <iostream>

int main()
{
	int r = 0, D = 0, X = 0;
	
	std::cin >> r >> D >> X;

	int ans = X;
	for (int i = 0; i < 10; i++)
    {
		ans = r * ans - D;
		std::cout << ans << std::endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rep1(i,n) for(int i = 1; i < n; i++)
#define repv(i,n) for(int i = n-1; i >= 0; i--)
#define fi first
#define sc second
#define pb push_back
using namespace std;
typedef long long ll;

char BUF[3500000];
inline void I(int&a){scanf("%d",&a);}
inline void I(int&a,int&b){scanf("%d%d",&a,&b);}
inline void I(int&a,int&b,int&c){scanf("%d%d%d",&a,&b,&c);}
inline void I(int&a,int&b,int&c,int&d){scanf("%d%d%d%d",&a,&b,&c,&d);}
inline void L(ll&a){scanf("%lld",&a);}
inline void L(ll&a,ll&b){scanf("%lld%lld",&a,&b);}
inline void L(ll&a,ll&b,ll&c){scanf("%lld%lld%lld",&a,&b,&c);}
inline void L(ll&a,ll&b,ll&c,ll&d){scanf("%lld%lld%lld%lld",&a,&b,&c,&d);}
inline void S(string&str){str.clear();scanf("%s",BUF);int s=strlen(BUF);rep(i,s)str.pb(BUF[i]);}
inline void SV(vector<int>&v){v.clear();scanf("%s",BUF);int s=strlen(BUF);rep(i,s)if('a'<=BUF[i]&&BUF[i]<='z')v.pb(BUF[i]-'a');else v.pb(BUF[i]-'A');}

const auto EPS = 1e-10;
const auto INF = 100000000;
const auto MOD = 1000000007;
typedef pair<ll,ll> P;

ll n;
int m, q;
int a[100000];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
bool b[7][100000], c[7][200000];

ll dfs1(int h){
    ll ret = 0;
    queue<int> que;
    rep(i,h) rep(j,7){
        if(!b[j][i]){
            ret++;
            que.push(i*7+j);
            while(que.size() != 0){
                int x = que.front()%7, y = que.front()/7; que.pop();
                rep(k,4){
                    int yy = y+dy[k], xx = x+dx[k];
                    if(yy < 0 || xx < 0 || yy >= h || xx >= 7) continue;
                    if(b[xx][yy]) continue;
                    b[xx][yy] = true;
                    que.push(yy*7+xx);
                }
            }
        }
    }
    return ret;
}

ll dfs2(int h){
    ll ret = 0;
    queue<int> que;
    rep(i,h) rep(j,7){
        if(!c[j][i]){
            ret++;
            que.push(i*7+j);
            while(que.size() != 0){
                int x = que.front()%7, y = que.front()/7; que.pop();
                rep(k,4){
                    int yy = y+dy[k], xx = x+dx[k];
                    if(yy < 0 || xx < 0 || yy >= h || xx >= 7) continue;
                    if(c[xx][yy]) continue;
                    c[xx][yy] = true;
                    que.push(yy*7+xx);
                }
            }
        }
    }
    return ret;
}

int main(){
    L(n); I(m,q);
    rep(i,q) I(a[i]);
    if(m%7 == 0){
        rep(i,q){
            b[a[i]%7][a[i]/7] = true;
            c[a[i]%7][a[i]/7] = true;
            c[a[i]%7][a[i]/7+m/7] = true;
        }
        ll x = dfs1(m/7);
        ll y = dfs2(2*m/7);
        cout << x+(y-x)*(7*n/m-1) << endl;
    } else{
        rep(i,q){
            rep(j,7){
                int tmp = a[i]+m*j;
                b[tmp%7][tmp/7] = true;
                c[tmp%7][tmp/7] = true;
                c[tmp%7][tmp/7+m] = true;
            }
        }
        ll x = dfs1(m);
        ll y = dfs2(2*m);
        cout << x+(y-x)*(n/m-1) << endl;
    }
}
































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

int main() {
    int N;
    int T[1000],A[1000];
    cin >> N;
    for(int i=0; i<N; ++i) cin >> T[i] >> A[i];
    long long PT[1000], PA[1000];
    PT[0] = T[0];
    PA[0] = A[0];
    for(int i=1; i<N; ++i) {
        if(PT[i-1] % T[i]) PT[i] = PT[i-1] + T[i] - PT[i-1] % T[i];
        else PT[i] = PT[i-1];
        long long t = PT[i] / T[i];
        if(PA[i-1] % A[i]) PA[i] = PA[i-1] + A[i] - PA[i-1] % A[i];
        else PA[i] = PA[i-1];
        long long a = PA[i] / A[i];
        if(t >= a) PA[i] = A[i] * t;
        else PT[i] = T[i] * a;
    }
    cout << PT[N-1] + PA[N-1] << endl;
}

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

typedef complex<double> P;
const double eps = 1e-8;

bool equals(double a, double b) {
  return abs(a-b) < eps;
}

double cross(P a, P b) {
  return a.real()*b.imag() - a.imag()*b.real();
}

double dot(P a, P b) {
  return a.real()*b.real() + a.imag()*b.imag();
}

double getDistanceLP(P s1, P s2, P p) {
  return abs(cross(s2-s1, p-s1)/abs(s2-s1));
}

double getDistanceSP(P s1, P s2, P p) {
  if(dot(s2-s1, p-s1) < 0.0) return abs(p-s1);
  if(dot(s1-s2, p-s2) < 0.0) return abs(p-s2);
  return getDistanceLP(s1, s2, p);
}

const int MAXN = 100;
int n;
P w[MAXN];
double r[MAXN];
int m;

bool safe(const P &t, const P &s) {
  for(int i = 0; i < n; ++i) {
    bool a, b;
    a = abs(w[i]-t) < r[i];
    b = abs(w[i]-s) < r[i];
    if(a ^ b) return true;
    if(!a) {
      double dist = getDistanceSP(t, s, w[i]);
      if(equals(dist, r[i]) || dist < r[i]) return true;
    }
  }
  return false;
}

int main() {
  while(cin >> n && n) {
    for(int i = 0; i < n; ++i) {
      cin >> w[i].real() >> w[i].imag() >> r[i];
    }
    cin >> m;
    while(m--) {
      P t, s;
      cin >> t.real() >> t.imag() >> s.real() >> s.imag();
      if(safe(t,s)) cout << "Safe" << endl;
      else cout << "Danger" << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1240
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;

int main() {
	int n;
	cin >> n;
	vector<int> h(n);
	for (int i = 0; i < n; i++) {
		cin >> h[i];
	}

	vector<int> dp(n);
	dp[1] = abs(h[1] - h[0]);
	for (int i = 2; i < n; i++) {
		dp[i] = min(dp[i - 2] + abs(h[i] - h[i - 2]), dp[i - 1] + abs(h[i] - h[i - 1]));
	}

	cout << dp[n - 1] << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
typedef long long ll;
typedef double D;
struct P { D x, y; };

int main(){
    int n; cin >> n;
    vector<P> p(n);
    rep(i, n) cin >> p[i].x >> p[i].y;

    auto dist = [&](P a, P b){
        return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
    };

    auto f1 = [&](D x, D y){
        D res = 0;
        rep(i, n) res = max(res, dist(P{x, y}, p[i]));
        return res;
    };

    auto f2 = [&](D x){
        D l = 0, r = 1005;
        rep(i, 100){
            D m1 = (l*2+r)/3;
            D m2 = (l+r*2)/3;
            if(f1(x, m1) > f1(x, m2)) l = m1;
            else r = m2;
        }
        return f1(x, l);
    };

    D l = 0, r = 1005;
    rep(i, 100){
        D m1 = (l*2+r)/3;
        D m2 = (l+r*2)/3;
        if(f2(m1) > f2(m2)) l = m1;
        else r = m2;
    }

    D ans = f2(l);
    printf("%.10f\n", ans);
}


Measured memory_bytes: 256
/**
 *    author:  tourist
 *    created: 21.09.2019 15:39:25       
**/
#include <bits/stdc++.h>

using namespace std;

template <typename T, class F = function<T(const T&, const T&)>>
class SparseTable {
 public:
  int n;
  vector<vector<T>> mat;
  F func;

  SparseTable(const vector<T>& a, const F& f) : func(f) {
    n = static_cast<int>(a.size());
    int max_log = 32 - __builtin_clz(n);
    mat.resize(max_log);
    mat[0] = a;
    for (int j = 1; j < max_log; j++) {
      mat[j].resize(n - (1 << j) + 1);
      for (int i = 0; i <= n - (1 << j); i++) {
        mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
      }
    }
  }

  T get(int from, int to) const {
    assert(0 <= from && from <= to && to <= n - 1);
    int lg = 32 - __builtin_clz(to - from + 1) - 1;
    return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  SparseTable<int> smin(a, [&](int i, int j) { return min(i, j); });
  SparseTable<int> smax(a, [&](int i, int j) { return max(i, j); });
  vector<int> bad(n - 1);
  for (int i = 0; i < n - 1; i++) {
    bad[i] = (a[i] > a[i + 1]);
  }
  vector<int> pref(n);
  for (int i = 0; i < n - 1; i++) {
    pref[i + 1] = pref[i] + bad[i];
  }
  int ans = 0;
  int nosort = 0;
  for (int i = 0; i <= n - k; i++) {
    if (pref[i + k - 1] - pref[i] == 0) {
      nosort = 1;
      continue;
    }
    if (i > 0 && smin.get(i - 1, i + k - 2) == a[i - 1] && smax.get(i, i + k - 1) == a[i + k - 1]) {
      continue;
    }
    ++ans;
  }
  cout << ans + nosort << '\n';
  return 0;
}


Measured memory_bytes: 28800
//
// Created by Hideaki Imamura on 2020-03-19.
//
# include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair <ll, ll> l_l;
typedef pair<int, int> i_i;

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

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

# define EPS (1e-7)
# define INF (1e9)
# define PI (acos(-1))
//const ll mod = 1000000007;

int N;

int main() {
    cin >> N;

    ll x[10][10]; // x[i][j]: 先頭がiで末尾がjである奴の個数
    for (int i = 1; i < 10; ++i) {
        for (int j = 1; j < 10; ++j) {
            x[i][j] = 0;
            for (int n = 1; n <= N; ++n) {
                if (n % 10 == j) {
                    int y = n;
                    while (y > 9) y /= 10;
                    if (y == i) x[i][j]++;
                }
            }
        }
    }

    ll ans = 0;
    for (int i = 1; i < 10; ++i) {
        for (int j = 1; j < 10; ++j) {
            ans += x[i][j] * x[j][i];
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <string.h>
#include <math.h>
#include <cmath>
#include <vector>
#include <algorithm>
#define ll long long

using namespace std;

const long long mod = 1e9+7;

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

    if(a >= 13) cout << b << endl;
    else if(a >= 6) cout << b/2 << endl;
    else cout << 0 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  string S; cin >> S;
  vector<string> s = {"dream", "dreamer", "erase", "eraser"};
  queue<int> BFS;
  BFS.push(0);
  bool judge = 0;
  while(!BFS.empty()) {
    int x = BFS.front();
    BFS.pop();
    if(x == S.size()) {
      judge = 1;
      break;
    }
    for(string a : s) {
      if(S.substr(x, a.size()) == a) BFS.push(x + a.size());
    }
  }
  cout << (judge ? "YES" : "NO") << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 100000000;
#define rep1(i, n) for (ll i=0; i<(n); i++) 
#define rep2(i, k, n) for (ll i=k; i<(n); i++)
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; }


int main() {
    ll n, m;
    cin >> n >> m;
    vector<string> a(n), b(m);
    rep1(i, n) cin >> a[i];
    rep1(i, m) cin >> b[i];
    ll count;
    for (ll i=0; i+m-1<(n); i++){
        for (ll j=0; j+m-1<(n); j++){
            count = 0;
            for (ll k=0; k<(m); k++){
                for (ll l=0; l<(m); l++){
                    count += (b[k][l]==a[i+k][j+l]);
                }
            }
            if (count == m*m){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    //printf("%.12f", ans);
}

Measured memory_bytes: 3620
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int n;
long long a[200001];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]*=2;
        a[i]+=a[i-1];
    }
    long long A=*lower_bound(a,a+n+1,a[n]/2);
    long long B=*(lower_bound(a,a+n+1,a[n]/2)-1);
    cout<<min(a[n]-B*2,A*2-a[n])/2<<endl;
}

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

string S2, T;

int main() {
    cin >> S2;
    cin >> T;
    int l_S = S2.size(), l_T = T.size();
    vector<string> changed_sentences(0);
    
    for (int i = 0; i <= l_S - l_T; i++) {
        bool is_match = true;
        for (int j = 0; j < l_T; j++) {
            if(S2.at(i + j) != '?' && S2.at(i + j) != T.at(j)) {
                is_match = false;
                break;
            }
        }

        
        if (is_match) {
            string changed = S2;

            for (int k = 0; k < l_S; k++) {
                if (changed.at(k) == '?') {
                    changed.at(k) = 'a';
                }
            }
            for (int l = 0; l < l_T; l++) {
                changed.at(i + l) = T.at(l);
            }
            changed_sentences.push_back(changed);
        }
    }

    if (changed_sentences.size() == 0) {
        cout << "UNRESTORABLE" << endl;
    }
    else {
        cout << *min_element(changed_sentences.begin(), changed_sentences.end()) << endl;
    }
}

Measured memory_bytes: 256
from sys import stdin


def fetch_one_line():
    return stdin.readline().rstrip()


def fetch_int_input():
    return [int(s) for s in fetch_one_line().split()]


def fetch_inputs(times):
    return [fetch_one_line() for _ in range(times)]


def fetch_int_inputs(times):
    return [[int(s) for s in fetch_one_line()] for _ in range(times)]

num = fetch_one_line()
first_sentence, second_sentence = fetch_one_line().split()

answer = ""
for s1, s2 in zip(first_sentence, second_sentence):
   answer += s1 + s2

print(answer)



Measured memory_bytes: 38384
#include<iostream>
#include<iomanip>
#include<string>
#include<algorithm>
#include<vector>
#include<utility>
#include<tuple>
#include<map>
#include<queue>
#include<stack>
#include<deque>
#include<bitset>
#include<math.h>
using namespace std;
using ll = int64_t;
using Graph = vector<vector<int> >;
const ll M = 1000000007;

int main(){
    int n;
    string s;
    cin >> n >> s;

    vector<int> w(n,0);
    vector<int> e(n,0);
    int cntw=0,cnte=0;
    for(int i=0;i<n;i++){
        if(s.at(i)=='W')cntw++;    
        w.at(i)=cntw;
    }

    for(int i=n-1;i>=0;i--){
        if(s.at(i)=='E')cnte++;
        e.at(i)=cnte;
    }

    int ans=n;
    for(int i=0;i<n;i++){
        int tmp=e.at(i)+w.at(i)-1;
        ans=min(ans,tmp);
    }

    cout << ans << endl;
}

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

int main(void){
  vector<int> data(10);
  for(int i=0;i<10;i++){
    cin >> data[i];
  }

  sort(data.begin(),data.end());
  for(int i=9;i>=7;i--){
    cout << data[i] << endl;
  }
  return 0;
}



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

int main(){
  int n;
  cin >> n;
  vector<vector<vector<int>>> data(4, vector<vector<int>>(3, vector<int>(10, 0)));
  for(int i = 0; i < n; i++){
    int b, f, r, v;
    cin >> b >> f >> r >> v;
    data.at(b - 1).at(f - 1).at(r - 1) += v;
  }
  for(int i = 0; i < 4; i++){
    for(int j = 0; j <= 3; j++){
      if(j == 3){ 
        if(i == 3){
          break;
        }
        else{ 
          cout << "####################" << endl;
          continue;
        }
      }

      for(int k = 0; k < 10; k++){
        if(k == 9){
          cout << " " << data.at(i).at(j).at(k) << endl;
        }
        else{
          cout << " " << data.at(i).at(j).at(k);
        }
      }
    }
  }
}



Measured memory_bytes: 3148
#include<bits/stdc++.h>
using namespace std;
int n, k, p[200005];

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

//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);

    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }

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

    for (int i = 1; i <= n - k; i++) {
        sum = sum - p[i - 1] + p[i + k -1];
        best = max(best, sum);
    }

    cout << fixed << setprecision(8);
    cout << (best + k) / 2. << '\n';
}


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

using namespace std;
using ll = long long;

int init();
int solve();

#define rep(i, a) for (int i = 0; i < (int) (a); i++)
#define reps(i, a, b) for (int i = (int) (a); i < (int) (b); i++)
#define rrep(i, a) for (int i = (int) a-1; i >= 0; i--)
#define rreps(i, a, b) for (int i = (int) (a)-1; i >= (int) (b); i--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}
#define TRUE__  "Yes"
#define FALSE__ "No"
#define PERM(v) next_permutation(all(v))
#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())
#define CIN(type, x) type x;cin >> x

#ifdef LOCAL
#define lcout(a) cout << a
#define lcoutln(a) cout << a << endl
#define lcerr(a) cerr << a
#define lcerrln(a) cerr << a << endl
#else
#define lcout(a) 
#define lcoutln(a) 
#define lcerr(a) 
#define lcerrln(a) 
#endif
#define MOD 1000000007
#define PI 3.141592653589793238462643383

signed main()
{
	init();
	solve();
}

string s;
int l;

int init()
{
	cin >> s;
	l = s.length();
	return 0;
}

void solve2()
{
	cout << s;
	int x[26];
	rep(i, 26) x[i] = 0;
	rep(i, l) {
		x[s[i] - 'a'] = 1;
	}
	rep(i, 26) {
		if (x[i] == 0) {
			cout << (char) (i + 'a') << endl;
			return;
		}
	}
}

bool ch()
{
	string t = "";
	rep(i, 26) t += (char) ('z' - i);
	if (t == s) {
		cout << -1 << endl;
		return true;
	}
	return false;
}

int solve()
{
	if (l != 26) {
		solve2();
		return 0;
	}
	if (ch()) return 0;
	int pos;
	for (pos = l-2; s[pos] > s[pos+1]; pos--);
	rep(i, pos) cout << s[i];
	rrep(i, l) {
		if (s[pos] < s[i]) {
			cout << s[i] << endl;
			return 0;
		}
	}
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ljc 998244353
using namespace std;
#define gc getchar
inline ll read(){
    register ll x=0,f=1;char ch=gc();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=gc();}
    while (isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=gc();}
    return (f==1)?x:-x;
}
ll ans[1010][1010],n;
bool vis[10101];
int tot,p[10101];
inline void init(int n){
	for (int i=2;i<=n;i++){
		if (!vis[i]) p[++tot]=i;
		for (int j=1;j<=tot;j++){
			if (1ll*i*p[j]>n) break;
			vis[i*p[j]]=1;
			if (i%p[j]==0) break;
		}
	}
}
inline ll lcm(ll a,ll b){
	if (a*b==0) return a+b;
	return a/__gcd(a,b)*b;
}
signed main(){
	n=read();
	if (n==2){
		printf("4 7\n23 10\n");
		return 0;
	}
	init(10000);
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			if ((i+j)%2==0){
				ans[i][j]=1ll*p[(i+j)/2]*p[1+(i-j)/2+n];
			}		
		}
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			if ((i+j)%2){
				ans[i][j]=1+lcm(ans[i-1][j],lcm(ans[i][j-1],lcm(ans[i+1][j],ans[i][j+1])));
			}		
			printf("%lld ",ans[i][j]);
		}
		puts("");
	}
	return 0;
}


Measured memory_bytes: 7640
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cmath>

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

constexpr ll LLINF {1001002003004005006};//ll = 9*LLINF
constexpr int INTINF {1000000000};//int = 2*INTINF

#define  rep(i,n)   for(int i = 0; i < (n); ++i)
#define rrep(i,n)   for(int i = 1; i <= (n); ++i)
#define drep(i,n)   for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for(int i = s; i < t;  ++i)

template<typename T>
void maxs(T& x, T&& y) {
  x=std::max(x,y);
}
template<typename T>
void maxs(T& x, T& y) {
  x=std::max(x,y);
}

template<typename T>
void mins(T& x, T&& y) {
  x=std::min(x,y);
}
template<typename T>
void mins(T& x, T& y) {
  x=std::min(x,y);
}

int main() {
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int N, M, C;
  cin >> N >> M >> C;
  vector<int> B(M);
  rep(i, M) cin >> B[i];
  vector<vector<int>> A(N, vector<int>(M));
  rep(i, N) {
    rep(j, M) cin >> A[i][j];
  }

  int cnt {};
  rep(i, N) {
    int answer {};
    rep(j, M) answer += A[i][j]*B[j];
    if (answer + C > 0) ++cnt;
  }
  cout << cnt << '\n';
}


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

using namespace std;

int main() {
	int n; scanf("%d", &n);
	int h[n];
	int dp[n];

	for(int i=0; i<n; i++)
		scanf("%d", &h[i]);

	dp[0] = 0;
	dp[1] = abs(h[1]-h[0]);

	for(int i=2; i<n; i++) {
		dp[i] = min(abs(h[i]-h[i-1]) + dp[i-1], 
					abs(h[i]-h[i-2]) + dp[i-2]);
	}

	printf("%d\n", dp[n-1]);

	return 0;
}

Measured memory_bytes: 1024