akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100005;
LL read(){
	LL x=0,f=1;
	char ch=getchar();
	while (!isdigit(ch)&&ch!='-')
		ch=getchar();
	if (ch=='-')
		f=-1,ch=getchar();
	while (isdigit(ch))
		x=(x<<1)+(x<<3)+ch-48,ch=getchar();
	return x*f;
}
int n,m;
LL k;
char S[N],T[N];
LL gcd(LL a,LL b){
	return b?gcd(b,a%b):a;
}
LL lcm(LL a,LL b){
	return a/gcd(a,b)*b;
}
map <LL,int> Map;
bool check(){
	Map.clear();
	for (int i=1;i<=n;i++)
		Map[(i-1)*(k/n)+1]=S[i];
	for (int i=1;i<=m;i++){
		if (Map[(i-1)*(k/m)+1]!=0&&Map[(i-1)*(k/m)+1]!=T[i])
			return 0;
	}
	return 1;
}
int main(){
	n=read(),m=read();
	scanf("%s%s",S+1,T+1);
	k=lcm(n,m);
	if (check())
		cout << k << endl;
	else
		cout << -1 << endl;
	return 0;
}

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

int main() {
  int N;
  int A;
  int B;
  
  cin >> N >> A >> B;
  int a_charge = A * N;
  if (a_charge > B) {
    cout << B << endl;
  }
  else {
    cout << a_charge << endl;
  }
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

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

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;
constexpr double EPS = 1e-10;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

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

    int h, w; cin>>h>>w;
    vector<vector<int>> a(h, vector<int>(w)), b(h, vector<int>(w));
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++) cin>>a[i][j];
    }
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++) cin>>b[i][j];
    }

    vector<vector<vector<bool>>> dp(h, vector<vector<bool>>(w, vector<bool>(15000, false)));
    dp[0][0][7500 + abs(a[0][0] - b[0][0])] = true;
    dp[0][0][7500 - abs(a[0][0] - b[0][0])] = true;

    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            int cur = abs(a[i][j] - b[i][j]);
            if(0 < i){
                for(int k=0; k<15000; k++){
                    int delta = k + cur;
                    if(dp[i-1][j][k] && delta < 15000) dp[i][j][delta] = true;
                    delta = k - cur;
                    if(dp[i-1][j][k] && 0 <= delta) dp[i][j][delta] = true;
                }
            }
            if(0 < j){
                for(int k=0; k<15000; k++){
                    int delta = k + cur;
                    if(dp[i][j-1][k] && delta < 15000) dp[i][j][delta] = true;
                    delta = k - cur;
                    if(dp[i][j-1][k] && 0 <= delta) dp[i][j][delta] = true;
                }
            }
        }
    }

    int ans = inf;
    for(int i=0; i<15000; i++){
        if(dp[h-1][w-1][i]){
            chmin(ans, abs(i - 7500));
        }
    }

    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 12544
#include "iostream"
#include "algorithm"
#include "string"
#include "vector"
#include "cmath"
#include "bitset"
#include "queue"
#include "functional"
#include "map"
#include "unordered_map"
#include "set"
#include "stack"
 
#define lp(n) for (int i = 0; i < n; i++)
#define LP(n,i) for (int i = 0; i < n; i++)
#define mod 1000000007
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define nyan "(=^･ω･^=)"
typedef long long ll;
using namespace std;

int n,d[13],mem,mx,mem2;
bool p[24],memp[24];
int main(){
	cin>>n;
	lp(12)
		d[i]=0;
	lp(n){
		cin>>mem;
		if(mem==0){
			cout<<0<<endl;
			return 0;
		}
		d[mem]++;
	}
	if(d[0]>=1||d[12]>=2){
		cout<<0<<endl;
		return 0;
	}
	lp(24)
		p[i]=false;
	p[0]=true;
	if(d[12]==1)
		p[12]=true;
	lp(12){
		if(d[i]>=3){
			cout<<0<<endl;
			return 0;
		}
		if(d[i]==2){
			p[i]=p[24-i]=true;
		}
	}
	mx=0;
	lp((1<<12)-1){
		LP(24,j)
			memp[j]=p[j];
		mem=i;
		LP(12,j){
			if(d[j]==1){
				if(mem%2==1)
					memp[j]=true;
				else
					memp[(24-j)%24]=true;
			}
			mem/=2;
		}
		mem=-10000;
		mem2=100;
		LP(24,j){
			if(memp[j]){
				mem2=min(mem2,j-mem);
				mem=j;
			}
			mem2=min(mem2,24-mem);
		}
		mx=max(mx,mem2);
	}
	cout<<mx<<endl;
	return 0;
}


Measured memory_bytes: 384
# -*- coding: utf-8 -*-

counter = [[[0] * 10 for i in range(4)] for k in range(5)]
# counter = [[[0] * 10] * 3] * 4

n = int(input())
for _ in range(n):
    b, f, r, v = list(map(int, input().split()))
    b -= 1
    f -= 1
    r -= 1
    counter[b][f][r] += v

x = 0
for i in range(4):
    if x != 0:
        print("#" * 20)
    x += 1

    for a in range(3):
        for b in range(10):
            print(" {}".format(counter[i][a][b]), end="")
        print()



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

#define fst() ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define f(i,a,b) for(i=a;i<b;i++)
#define pb push_back
#define mp make_pair
#define endl '\n'
typedef long long ll;

int main()
{
  fst();
  int n,a;
  cin>>n>>a;
  if(a-(n%500)>=0) cout<<"Yes";
  else cout<<"No";
  return 0;
}


Measured memory_bytes: 256
n, m = map(int, input().split())
S = [list(map(int, input().split()))[1:] for _ in range(m)]
P = list(map(int, input().split()))
  
ans = 0
for b in range(2 ** n):
  onswitch = [i + 1 for i in range(n) if (b >> i) & 1]
  if all(sum(o in s for o in onswitch) % 2 == p for s, p in zip(S, P)):
    ans += 1
    
print(ans)

Measured memory_bytes: 9136
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
int main(){
  
    string noun;

	cin>>noun;

	int n;

	n = noun.length();

	if(noun[n-1] == 's')cout<<noun+"es"<<endl;
    else cout<<noun+'s'<<endl;

	return 0;
}

Measured memory_bytes: 3556
sub f{
	my($t,$s)=@_;
	$v[$_]=$t;
	grep$v[$_]?$v[$_]&$t:f(3-$t),@$_;
}
@n=1..<>;
map{push@$_,$_[--$|]for@_=split$"}<>;
$v[$_]||${@$_?f(1)?b:a:c}++for@n;
print@n*2*$c-$c*$c+2*$a*$a+$b*$b+2*$a*$b

Measured memory_bytes: 158336
num = list(map(int,input().split()))


for i in range(2,0,-1):
    k = 0
    while k < i:
        if num[k] > num[k+1]:
             num[k],num[k+1] = num[k+1],num[k]
        k += 1;


for l in range (len(num)-1):
    print(num[l],end=" ")
    
print(num[len(num)-1])


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



void solve()
{
    int t,n,m,i,k,r,l,u,v,w,j,s,sum=0,pos,flag=0,count=0;
    string S,T,U; 
    // int a,b,c;
    cin>>n;
    m=100;
    while(m<n)
    {
        m+=m/100;
        count++;
    }
    cout<<count;
}
 
 
signed main()
{
    #ifndef ONLINE_JUDGE 
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
    #endif
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)
    {
        solve();
        if(t)cout<<"\n";
    }
    return 0;
}

Measured memory_bytes: 3576
import java.util.*;
class Main {
	static int n;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			n = sc.nextInt();
			if (n == 0) break;
			int maxDistance = 0;
			Map<Integer, Integer> map = new HashMap<Integer, Integer>();
			for (int i = 0; i < n; i++) {
				int p = sc.nextInt();
				int d = sc.nextInt() + sc.nextInt();
				map.put(d, p);
				maxDistance = Math.max(d, maxDistance);
			}
			System.out.printf("%d %d\n", map.get(maxDistance), maxDistance);
		}
	}
}

Measured memory_bytes: 17000
#include<stdio.h>
#define N 8
 
int Q[N][N];
 
int putQueen(int *,int *,int );
 
void print();

int main(){
 
  int i,j;
  int n,k;
  int r[N],c[N];
 
  for(i = 0;i < N;i ++)
    {
      r[i] = 0;
      c[i] = 0;
    
      for(j = 0;j < N;j ++)
	{
	  Q[j][i] = 0;
	}
    }
 
  scanf("%d",&n);

  k = n;
 
  for(i = 0;i < n;i ++)
    {
      scanf("%d%d",&r[i],&c[i]);
    }
  
  while(k < N){

    if(c[k] == N-1)
      {
	r[k] ++;
	c[k] = 0;
      }
    else
      c[k] ++;
 
    if(r[k] > N-1)
      {
	r[k] = 0;
	c[k] = 0;
	k--;
      }
    
    else if(putQueen(r,c,k))
      k ++;
  }
 
  for(i = 0;i < N;i ++)
    {
      Q[c[i]][r[i]]=1;
    }
  
  print();
 
  return 0;
}

int putQueen(int *r,int *c,int k){

  int i;
 
  for(i = 0;i < k;i ++)
    {
      if(r[i] == r[k])return 0;

      if(c[i]==c[k])return 0;
    
      if(r[i] + c[i] == r[k] + c[k])return 0;
    
      if(r[i]-c[i] == r[k] - c[k])return 0;
    }
  return 1;
}
 
void print(){

  int i,j;
 
  for(i = 0;i < N;i ++)
    {
      for(j = 0;j < N;j ++)
	{
	  if(Q[j][i] == 1)printf("Q");
	  else{
	    printf(".");
	  }
	}
      printf("\n");
    }
}

Measured memory_bytes: 572
INF = float("inf")
cnt = 0
def merge(A, left, mid, right):
    global cnt
    L = A[left: mid] + [INF]
    R = A[mid: right] + [INF]
    i = j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            cnt += j
            i += 1
        else:
            A[k] = R[j]
            j += 1
def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
n = int(input())
S = list(map(int, input().split()))
mergeSort(S, 0, n)
print(cnt)



Measured memory_bytes: 27480
import java.util.*;
public class Main {
public static void main(String[] args) {
		int x = 0;
		int y = 0;
		Scanner scan = new Scanner(System.in);
		x = scan.nextInt();
		y = scan.nextInt();
		
		int result = x+ y/2;
		System.out.println(result);
	}
}

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

const int N = 1e5 + 5;

set <int> s;
int h[N];
int dp[N];

int main()
{
	int n, k;
	cin >> n >> k;
	
	for(int i = 0; i < n; i++)
	{
		cin >> h[i];
	}
	
	for(int i = 1; i <= k; i++)
	{
		dp[i] = abs(h[i] - h[0]);
	}
	
	for(int i = k + 1; i < n; i++)
	{
		dp[i] = 1e9;
		for(int j = i - 1; j >= i - k; j--)
		{
			dp[i] = min(dp[j] + abs(h[i] - h[j]) , dp[i]);
		}
	}
	
	cout << dp[n - 1];
	
	return 0;
}

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

#define len_MAX 5000000
int A[len_MAX+1];

void Z_algorithm(string S){
    A[0] = S.size();
    int i = 1, j = 0;
    while (i < S.size()) {
        while (i+j < S.size() && S[j] == S[i+j]) ++j;
        A[i] = j;
        if (j == 0) { ++i; continue;}
        int k = 1;
        while (i+k < S.size() && k+A[k] < j) A[i+k] = A[k], ++k;
        i += k; j -= k;
    }
}

int main(){
    //input
    string S,T;
    cin >> S >> T;

    //calc
    int n=S.length(), m=T.length();
    string S_ext,U;
    while(S_ext.length()<m){
        S_ext += S;
    }
    S_ext += S_ext;
    U += T;
    U += '_';
    U += S_ext;
    Z_algorithm(U);
    bool in[n], out[n], visited[n];
    int i,j;
    for(i=0; i<n; i++){
        in[i]=0;
        out[i]=0;
        visited[i]=0;
    }
    for(i=0; i<n; i++){
        if(A[i+(m+1)]==m){
            out[i]=1;
            in[(i+m)%n]=1;
        }
    }
    //dfs
    int ans=0, val;
    for(i=0; i<n; i++){
        if(out[i]==1&&in[i]==0){
            visited[i]=1;
            val=1;
            j = (i+m)%n;
            while(out[j]==1){
                visited[j]=1;
                val++;
                j = (j+m)%n;
            }
            ans=max(ans,val);
        }
    }
    bool loop=0;
    for(i=0; i<n; i++){
        if(visited[i]==0&&out[i]==1){
            loop=1;
        }
    }

    //output
    if(loop==1){
        cout << -1 << endl;
    }else{
        cout << ans << endl;
    }
    system("pause");
    return 0;
}

Measured memory_bytes: 21760
#include <bits/stdc++.h>
#include <iomanip>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
using vi=vector<int>;
int main() {
	// your code goes here
	fast;
	int n;
	cin>>n;
	vi arr(n);
	for(int i=0;i<n;i++) cin>>arr[i];
	sort(arr.begin(),arr.end());
	std::cout<<std::setprecision(5);
	//cout<<std::fixed;
	float ans=((float)(arr[0]+arr[1])/2.0);
	for(int i=2;i<n;i++){
		ans=((float)(arr[i]+ans)/2.0);
	}
	cout<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {

        solve_149_D();
      
        return;
    }

    private static void solve_149_D() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] score = new int [N];
        int K = sc.nextInt();

        int R_point = sc.nextInt();
        int S_point = sc.nextInt();
        int P_point = sc.nextInt();

        String T = sc.next();
        String[] TArray = T.split("");

        for(int i=0; i<N; i++) score[i] = 0;

        if(TArray[0].equals("r")){
            score[0] = P_point;
        }else if(TArray[0].equals("s")){
            score[0] = R_point;
        }else {
            score[0] = S_point;
        }

        for(int i=1; i<N; i++){
            if( (i-K)<0 ){
                if(TArray[i].equals("r")){
                    score[i] = score[i-1]+P_point;
                }else if(TArray[i].equals("s")){
                    score[i] = score[i-1]+R_point;
                }else {
                    score[i] = score[i-1]+S_point;
                }
            }else{
                if((TArray[i-K].equals(TArray[i])) && ((i-K)==0)  ){
                    score[i] = score[i-1]+0;
                }else if((TArray[i-K].equals(TArray[i])) && (score[i-K]!=score[i-K-1])  ){
                    score[i] = score[i-1]+0;
                }else{
                    if(TArray[i].equals("r")){
                        score[i] = score[i-1]+P_point;
                    }else if(TArray[i].equals("s")){
                        score[i] = score[i-1]+R_point;
                    }else {
                        score[i] = score[i-1]+S_point;
                    }
                }
            }
        }
        System.out.println(score[N-1]);
    }
}

Measured memory_bytes: 34008
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Ac//赚钱
{
    long M[11];
};

int S(const void *a,const void *b)
    {
        return *(int*)b-*(int*)a;
    }

struct Time//时间
{
    long as[10];
};



int main()
{
    long H[1024],k,R[100],t,n;
    long p[1024][10];
    struct Time mar[100];
    struct Ac ac[100];
    long i,j;
    long q;
    for(n=1;n<1024;n++)
    {
        k=n;
        for(i=0;i<10;i++)
        {
            t=pow(2,9-i);
            if(k/t!=1)
                p[n-1][i]=0;
            else
                p[n-1][i]=1;
            k%=t;
        }
    }
    
    scanf("%ld",&k);
    for(i=0;i<k;i++)
    {
        for(j=0;j<10;j++)
        {
            scanf("%ld",&mar[i].as[j]);
        }
    }//第一次输入
    for(i=0;i<k;i++)
    {
        for(j=0;j<11;j++)
        {
            scanf("%ld",&ac[i].M[j]);
        }
    }//第二次输入
    for(n=1;n<1024;n++)
    {
        for(i=0;i<k;i++)
        {
            R[i]=0;
        }
        for(i=0;i<10;i++)
        {
            for(j=0;j<k;j++)
            {
                if(mar[j].as[i]==1&&p[n-1][i]==1)
                    R[j]++;
            }
        }
        q=0;
        for(i=0;i<k;i++)
        {
            q=q+ac[i].M[R[i]];
        }
        H[n-1]=q;
    }
    qsort(H,1023,sizeof(H[0]),S);
    printf("%ld",H[0]);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <string>

using namespace std;

using s64 = long long int;

struct R {
    string name;
    int point;
    int no;
};

int main(){
    std::vector<R> data;

    int N;
    cin >> N;
    for(int i=0;i<N;i++){
        R r;
        cin >> r.name >> r.point;

        r.no = i + 1;

        data.push_back(r);
    }

    sort(data.begin(), data.end(), [](R l, R r) {
            if(l.name == r.name){
                return l.point > r.point;
            }else{
                return l.name < r.name;
            }
            });

    for(int i=0;i<N;i++){
        cout << data[i].no << endl;
    }

    return 0;
}



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

int main() {
  int hour;
  int minute;
  int second;
  scanf("%d", &second);

  hour = floor(second / 3600);
  second = second % 3600;

  minute = floor(second / 60);
  second = second % 60;

  printf("%d:%d:%d\n", hour, minute, second);
  return 0;
}

Measured memory_bytes: 592
class dice:
    def __init__(self,label):
        self.top, self.front, self.right, self.left, self.rear, self.bottom \
                = label
 
    def roll(self,op):
        if   op=='N': self.top, self.front, self.bottom, self.rear = \
                                self.front, self.bottom, self.rear , self.top
        elif op=='E': self.top, self.left , self.bottom, self.right = \
                                self.left , self.bottom, self.right, self.top
        elif op=='W': self.top, self.right, self.bottom, self.left = \
                                self.right, self.bottom, self.left , self.top
        elif op=='S': self.top, self.rear , self.bottom, self.front = \
                                self.rear , self.bottom, self.front, self.top
 
    def print_top(self): print(self.top)
    def print_right(self): print(self.right)
 
    def get_label(self):
        return [self.top, self.front, self.right, self.left, self.rear, self.bottom]
  
label = list(map(int,input().split()))
d = dice(label)
q = int(input())
for _ in range(q):
    top_front = [int(x) for x in input().split()]
    for op in 'EEENEEENEEESEEESEEENEEEN':
        if d.get_label()[:2] == top_front:
            d.print_right()
            break
        d.roll(op)

Measured memory_bytes: 7728
#define _USE_MATH_DEFINES
#include <math.h>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>

using namespace std;
typedef long long ll;

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

int main() {

    ll X;
    cin >> X;
    ll out = 0;
    out = X/500*1000 + (X%500)/5*5;
    cout << out << endl;
    return 0;
}


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

#define reps(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   reps(i,0,n)
#define all(x) (x).begin(),(x).end()
#define INF (1000000000)
#define MOD (1000000007)
#define PI (acos(-1))

int main(){
  int N,K;
  cin >> N >> K;
  double ans=0;
  reps(i,1,N+1){
    if(i>=K){
      ans+=1;
    }else{
      int tmp = i;
      int cnt=0;
      while(1){
        tmp *= 2;
        cnt++;
        if(tmp>=K)break;
      }
      ans += (double)(1/pow(2,cnt));
    }
  }
  ans /= N;
  cout << fixed << setprecision(15) << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
	int a, b;
	cin >> a >> b;
	if (a - (b * 2) <= 0) {
		cout << "0" << endl;
	}
	else {
		cout << a - b * 2 << endl;
	}
	//cout << a - b * 2 << endl;
}

Measured memory_bytes: 256
def main():
    from collections import deque
    n, q = map(int, input().split())
    g = [[] for i in range(n+1)]
    point = [0 for i in range(n+1)]
    for i in range(n-1):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)
    for i in range(q):
        p, x = map(int, input().split())
        point[p] += x

    q = deque([[1,0]])
    for j in range(n):
        now = q.pop()
        point[now[0]] += point[now[1]]
        for i in g[now[0]]:
            if i==now[1]:
                continue
            q.append([i,now[0]])
    for i in range(1, n+1):
        print(point[i], end='')
        if i!=n:
            print(' ', end='')

if __name__ == '__main__':
    main()


Measured memory_bytes: 63180
grid = [list(map(int, input().split())) for _ in range(3)]
B = [x for x in grid[0]]
b = B[0]
A = [grid[i][0] - b for i in range(3)]
res = True
for i, a in enumerate(A):
    for j, b in enumerate(B):
        if grid[i][j] != a + b:
            res = False
            break
    else:
        continue
    break
print('Yes' if res else 'No')


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;

int main(){
  int n;
  cin >> n;
  vi a(n+1);
  rep(i,n) cin >> a[i+1];
  map<int, int> mp;
  ll ans=0;
  for(int i=1; i<=n; i++){
    int sa = i - a[i];
    ans += mp[sa];
    int wa = i + a[i];
    mp[wa]++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 20980
import java.util.*

fun main(args: Array<String>) {
    val scn = Scanner(System.`in`)
    val A = scn.nextInt()
    val B = scn.nextInt()
    val C = scn.nextInt()


    if(A==B && A!=C){
        println("Yes")
    }else if(A==C && A!=B){
        println("Yes")
    }else if(B==C && B!=A){
        println("Yes")
    }else{
        println("No")
    }

}



Measured memory_bytes: 29596
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
#include <tuple>
using namespace std;

#define rep(i,a) for(int i=0; i<a; i++)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define rep1(i,a) for(int i=1; i<=a; i++)
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define mem(a,n) memset( a, n, sizeof(a))
#define all(a) a.begin(),a.end()

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LLINF = 1e18;
static const double pi = 3.141592653589793;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N;
    cin>>N;
    
    string ans="";
    while(N!=0){
        int r = N%2;
        if(r<0) r+=2;
        
        N = (N-r)/(-2);
        ans += (char)('0'+r);
    }
    reverse(all(ans));
    
    if(ans=="") ans="0";
    cout1(ans);
}

Measured memory_bytes: 256
text = input()
count = int(input())

for c in range(count):
    args = input().split()
    (a, b) = [int(x) for x in args[1:3]]
    if args[0] == 'print':
        print(text[a:b + 1])
    elif args[0] == 'reverse':
        text = text[0:a] + text[a:b + 1][::-1] + text[b + 1:]
    elif args[0] == 'replace':
        text = text[0:a] +  args[3] + text[b + 1:]

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

#define ONLINE_JUDGE
#define pb(a) push_back(a)
#define all(a) (a.begin(), a.end())

using ll = long long;

const int E5 = 1e5;

//////////// Solution /////////////////////////////////

int N, xar[100], yar[100], har[100];

void solve() {
	cin >> N;
	for (int i = 0; i < N; ++i) {
		cin >> xar[i] >> yar[i] >> har[i];
	}

	for (int x = 0; x <= 100; ++x) {
		for (int y = 0; y <= 100; ++y) {

			int tmp = har[0] + abs(x-xar[0]) + abs(y-yar[0]);
			int i = 0;
			for (i = 0; i < N; ++i) {
				if (har[i] > 0) {
					tmp = har[i] + abs(x-xar[i]) + abs(y-yar[i]);
				}
			}

			for (i = 0; i < N; ++i) {
				if (max(0, tmp - abs(x-xar[i]) - abs(y-yar[i])) != har[i]) {
					break;
				}
			}

			if (i == N) {
				cout << x << ' ' << y << ' ' << tmp << '\n';
				return;
			}
		}
	}
}	

/////////// End Solution ///////////////////////////////////////

//////// Initialization ////////////////////////////////////

int main() {

	#ifndef ONLINE_JUDGE
	FILE *FIN = freopen("/home/danil/prog/input.txt", "r", stdin);
	clock_t time_start = clock();
	#endif

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

	solve();

	#ifndef ONLINE_JUDGE
	fclose(FIN);
	cerr << "\x1b[031m\n-----------------\nTime=" << (ll)((double)(clock()-time_start) / CLOCKS_PER_SEC * 1000) << "ms\n\x1b[0m";
	#endif

	return 0;
}

//////// End Initialization ///////////////////////////////////////

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

int main(void){

  char s[6];
  scanf("%s", s);
  for (int i = 1; i < strlen(s); i++) {
    if (s[i-1] == 'A' && s[i] == 'C') {
      printf("Yes\n");
      return 0;
    }
  }
  printf("No\n");

  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main(){
    int a,n,c=0,max=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a;
        if(a>=max) c++;
        if(a>max) max=a;
    }
    cout<<c<<"\n";
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	_ "container/heap"
	"fmt"
	"os"
	"sort"
	"strconv"
)

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func ceil(a, b int) int {
	if a%b == 0 {
		return a / b
	} else {
		return a/b + 1
	}
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func lcm(a, b int) int {
	return a / gcd(a, b) * b
}

// Sort
type RuneSlice []rune

func (a RuneSlice) Len() int           { return len(a) }
func (a RuneSlice) Less(i, j int) bool { return a[i] < a[j] }
func (a RuneSlice) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

// Main
const MOD = int(1e+9) + 7
const INF = 1 << 60

func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	defer wtr.Flush()
	N := sc.nextInt()
	set := make(map[string]int)
	for i := 0; i < N; i++ {
		set[sc.nextStr()]++
	}
	ans := []string{}
	mx := 0
	for _, num := range set {
		if mx < num {
			mx = num
		}
	}
	for key, num := range set {
		if mx == num {
			ans = append(ans, key)
		}
	}
	sort.Strings(ans)

	for i := 0; i < len(ans); i++ {
		fmt.Fprintln(wtr, ans[i])
	}
}


Measured memory_bytes: 29184
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vvvll = vector<vector<vector<ll>>>;
using vvvvll = vector<vector<vector<vector<ll>>>>;
using pl4 = pair<ll,ll>;
using str = string;
using vpl4 = vector<pair<ll,ll>>;

#define sz size()
#define be begin()
#define en end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

#define llin(x) ll (x);cin >>(x);
#define stin(x) str (x);cin >>(x);
#define vllin(x,n) vll (x)(n);FOR(i,0,n-1){cin >>(x)[i];}
#define vllin2(a,b,n) vll (a)(n);vll (b)(n);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i];}
#define vllin3(a,b,c,n) vll (a)(n);vll (b)(n);vll (c)(n);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i]>>(c)[i];}
#define vlling(x,n) (x).assign(n,0);FOR(i,0,n-1){cin >>(x)[i];}
#define vlling2(a,b,n) (a).assign(n,0);(b).assign(n,0);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i];}
#define vlling3(a,b,c,n) (a).assign(n,0);(b).assign(n,0);(c).assign(n,0);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i]>>(c)[i];}
#define vpl4in(x,n) vpl4 (x)((n),mp(0,0));FOR(i,0,n-1){cin >>x[i].fi>>x[i].se;}
#define FOR(i,a,b) for(ll i = a ; i <= b ; i++)
#define rFOR(i,b,a) for(ll i = a; i >= b ; i--)
#define SORT(x) sort(x.be, x.en)
#define rSORT(x) sort(x.rbegin(), x.rend())
#define say(x) cout<<(x);
#define sal(x) cout<<(x)<<endl;
#define says(x) cout<<(x)<<(' ');
#define sas cout<<(' ');
#define sayR(x) cout<<fixed<<setprecision(10)<<(x);
#define salR(x) cout<<fixed<<setprecision(10)<<(x)<<endl;
#define yn(a) cout <<((a)?"yes":"no")<<endl;
#define Yn(a) cout <<((a)?"Yes":"No")<<endl;
#define YN(a) cout <<((a)?"YES":"NO")<<endl;
#define Imp(a) cout <<((a)?"Possible":"Impossible")<<endl;
#define IMP(a) cout <<((a)?"POSSIBLE":"IMPOSSIBLE")<<endl;
#define pow(a,b) ll(pow(a,b))

ll MOD=1000000007;
ll INF=100000000000001;
vector<ll> value; // ノードの値を持つ配列
ll N;             // 葉の数
 
void update(ll i, ll x) {
    // i 番目の葉の値を x に変える
    i += N - 1; // i 番目の葉のノード番号
    value[i] = x;
    while (i > 0) {
        i = (i - 1) / 2; // ノード i の親ノードの番号に変える
        value[i] = min(value[i * 2 + 1],
                       value[i * 2 + 2]); // 左右の子の min を計算しなおす
    }
}
 
ll query(ll a, ll b, ll k, ll l, ll r) {
    // [a, b) の区間に対するクエリについて
    // ノード k （区間 [l, r) 担当）が答える
    if (r <= a || b <= l) return INF; // 区間が被らない場合は INF を返す
    if (a <= l && r <= b)
        return value[k]; // ノード k の担当範囲がクエリ区間 [a, b)
                         // に完全に含まれる
    else {
        ll c1 = query(a, b, 2 * k + 1, l, (l + r) / 2); // 左の子に値を聞く
        ll c2 = query(a, b, 2 * k + 2, (l + r) / 2, r); // 右の子に値を聞く
        return min(c1, c2); // 左右の子の値の min を取る
    }
}
signed main(){
    llin(h);
    llin(a);
    sal((h-1)/a+1)
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    string str;
    cin>>str;
    int len=str.size();
    int countp=0;
    for(auto c:str){
        if(c=='p'){
            countp++;
        }
    }
    cout<<(len/2)-countp<<endl;
}


Measured memory_bytes: 512
A,B,C = input().split()
A = int(A)
B = int(B)
C = int(C)

if A==B and B==C:
    print("No")
elif A==B:
    print("Yes")
elif B==C:
    print("Yes")
elif A==C:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 2940
#include <bits/stdc++.h>
  
using namespace std;
  
template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }
  
#define pb push_back
#define mp make_pair
#define cotu cout
#define itn int
#define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int i = 0; i < n; ++i)
#define repr(i,n) for(int i = n - 1; i >= 0; --i)
#define Rep(i, a, n) for(int i = (a); i <=(n); ++i)
#define repst(i, n) for(auto it = n.begin(); it != n.end(); ++it)
#define Repr(i, a, n) for(int i = (n); i >= (a); --i)
  
#define ordered_set tree<int , null_type,less<int >, rb_tree_tag,tree_order_statistics_node_update> 
  
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
  
const int inf = int(1e9);
const int mod = inf + 7;
const int N = 1e6 + 555; // TL MB
const double PI = acos(-1.0);
 
void mul(ll &x, ll y){
	x *= y;
	if(x >= mod) x %= mod;
}
 
void add(ll &x, ll y){
	x += y;
	if(x >= mod) x -= mod;
	if(x < 0) x += mod;
}
ll bp(ll a, ll n){
	ll r = 1;
	while(n){
		if(n & 1) mul(r, a);
		mul(a, a);
		n >>= 1;
	}
	return r;
}

void solve()
{
	int n;
	cin >> n;
	int a[n];
	int sum = 0;
	for(int i = 0; i < n; ++i) cin >> a[i], sum += a[i];
	int mn = inf;
	int x = 0;
	for(int i = 0; i < n; ++i){
		x += a[i];
		mn = min(mn, abs(2 * x - sum));
	}
	cout << mn;
}


 
 
int main()
{
    Red;
  	// int T; cin >> T; while(T--)
    solve();
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000

int digitsum(int a) {
    int ret = 0;
    while (a > 0) {
        ret += a % 10;
        a /= 10;
    }
    return ret;
}


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, A, B;
    cin >> N >> A >> B;

    int ans = 0;
    REP(i, 1, N) {
        int d = digitsum(i);
        if (A <= d && d <= B) ans += i;
    }
    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap



@mt
def slv(N, C, STC):
    from collections import Counter
    se = [(2*s, 0, c) for s, t, c in STC]
    te = [(2*t+1, 1, c) for s, t, c in STC]
    e = se + te
    e.sort(reverse=True)
    r = Counter()
    ans = 0
    while e:
        _, k, c = e.pop()
        if k == 0:
            r[c] += 1
        else:
            r[c] -= 1
            if r[c] == 0:
                r.pop(c)
        ans = max(ans, len(r))
    return ans


def main():
    N, C = read_int_n()
    STC = [read_int_n() for _ in range(N)]
    print(slv(N, C, STC))


if __name__ == '__main__':
    main()


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

long long int lcm(long long int a, long long int b) {
  long long int x;
  x = a * b;
  if(a<b) {
    long long int tmp = a;
    a = b;
    b = tmp;
  }
  long long int r = a % b;
  while(r!=0) {
    a = b;
    b = r;
    r = a % b;
  }
  return x / b;
}

int main() {
  long long int a, b, c, d;
  cin >> a >> b >> c >> d;
  long long int x, y, z, t1, t2;

  x = (a - 1) / c;
  y = (a - 1) / d;
  z = (a - 1) / lcm(c, d);
  t1 = (a - 1) - (x + y - z);
  
  x = b / c;
  y = b / d;
  z = b / lcm(c, d);
  t2 = b - (x + y - z);
  
  
  cout << t2 - t1 << endl;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define mk make_pair
#define pb push_back
#define ppb pop_back
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	string s,t;
	cin>>s>>t;
  int dp[3005][3005];
string ans;
	int n=s.size(),m=t.size();
	//for (int i=0;i<3005;i++) dp[i][0]=dp[0][i]=0;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			if(s[i-1]==t[j-1]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
	}
	int i=n,j=m;
	while(i>0 && j>0)
	{
		if (s[i-1]==t[j-1])
		{
			ans+=s[i-1];
			i--;
			j--;
		} else
		if (dp[i][j]==dp[i-1][j]) i--; else j--;
	}
	reverse(ans.begin(),ans.end());
	cout<<ans;
	return 0;
}

Measured memory_bytes: 35456
#include<stdio.h>
int main(){
    int a,b,c;
    while(scanf("%d%d%d",&a,&b,&c),a+b+c){
        c=100-c;
        int win=0;
        int mon=0;
        for(int i=0;i<a;i++){
            int d;
            scanf("%d",&d);
            if(b==i+1)win=d;
            mon+=c*d;
        }
        printf("%d\n",win?mon/win:0);
    }
}


Measured memory_bytes: 2556
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
//using Graph = vector<vector<int>>;
typedef long long ll;

//const double PI=acos(-1.0);

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

    priority_queue<ll> q;
    for(int i = 0; i < n; ++i) {
        ll a; cin >> a; q.push(a);
    }

    for(int i = 0; i < m; ++i) {
        ll t = q.top(); q.pop();
        q.push(t / 2);
    }

    ll sum = 0;
    while(!q.empty()) sum += q.top(), q.pop();

    cout << sum << endl;

    return 0;
}


Measured memory_bytes: 1400
#include<stdio.h>
int main(void) {
	int i,j,n, c[6] = {0};
	double h[40];

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

		if (h[i] < 165.0)
			c[0]++;
		else if (h[i] >= 165.0 && h[i] < 170.0)
			c[1]++;
		else if (h[i] >= 170.0 && h[i] < 175.0)
			c[2]++;
		else if (h[i] >= 175.0 && h[i] < 180.0)
			c[3]++;
		else if (h[i] >= 180.0 && h[i] < 185.0)
			c[4]++;
		else
			c[5]++;
	}
	for (i = 0; i < 6; i++) {
		printf("%d:",i+1);
		for (j = 0; j < c[i]; j++)
			printf("*");
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,l,r) for(ll i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(ll i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,n-1,0)
#define RREPS(i,n) RFOR(i,n,1)
#define pb push_back
#define eb emplace_back
#define SZ(x) ((ll)(x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
template<class T = ll> using V = vector<T>;
template<class T = ll> using VV = V<V<T>>;
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; }
inline void Yes(bool b = true) {cout << (b ? "Yes" : "No") << '\n';}
inline void YES(bool b = true) {cout << (b ? "YES" : "NO") << '\n';}
inline void err(bool b = true) {if(b) {cout << -1 << '\n'; exit(0);}}
template<class T> inline void fin(bool b = true, T e = 0) {if(b) {cout << e << '\n'; exit(0);}}
template<class T> T Roundup_div(T x, T y) {return (x+(y-1))/y;}
const ll INF = 1e18;
V<> VEC(ll n) {V<> v(n); REP(i, n) cin >> v[i]; return v;}
template <typename T> T pow(T a, long long n, T e = 1) {T ret = e; while (n) {if (n & 1) ret *= a; a *= a; n >>= 1;} return ret;}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    VV<> a(n);
    REP(i, n) a[i] = VEC(m);
    REP(i, n)REP(j, m) a[i][j]--;
    ll res = INF;
    V<bool> used(m, true);
    REP(k, m){
        V<> cnt(m, 0);
        REP(i, n){
            REP(j, m){
                if(used[a[i][j]]){
                    cnt[a[i][j]]++;
                    break;
                }
            }
        }
        ll MA = 0, num = -1;
        REP(i, m) if(chmax(MA, cnt[i])) num = i;
        chmin(res, MA);
        used[num] = false;
    }
    cout << res << '\n';
}

Measured memory_bytes: 4336
#[allow(unused)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};
 
    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };
 
    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };
 
    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };
 
    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };
 
    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused)]
macro_rules! out {
    ($x:expr) => {
        println!("{:?}", $x)
    };
}

fn main(){
    // have fun!
    input! {
        S: String
    }
    let S: String = S;
    let mut count = 0;
    for i in 0..S.len() {
        let head = i;
        let foot = (S.len() - 1) - i;
        // headよりfootが大きかったら
        if foot < head {
            break
        }
        // 比較
        if getChar(&S, head) != getChar(&S, foot){
            count += 1;
        }
        // headとfootが同じだったら
        if head == foot {
            break
        }
    }
    out! {
        count
    }
}


fn getChar(target: &String, index: usize) -> char{
    let c = target.chars().nth(index);
    c.unwrap()
}

#[test]
fn testGetChar() {
    let val = "abc".to_string();
    let c = getChar(&val, 1);

    assert_eq!(c, 'b');
}





Measured memory_bytes: 4352
#include "bits/stdc++.h"
using namespace std;
 
////////////// Prewritten code follows. Look down for solution. ////////////////

#define fs first
#define sc second
#define pb push_back
#define len(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

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

const ll LINF = 1e18;
const int INF = 1e9;
const int MOD = 1e9+7;

/// command for char arrays with spaces -> scanf(" %[^\n]", texto);
 
////////////////////////// Solution starts below. //////////////////////////////

int main(){

	int n;
	int sum = 0;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		sum += i;
	}
	printf("%d\n", sum);
	return 0;
}

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

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n);
    vector<int> b(m);
    rep(i,n) cin >> a[i];
    rep(i,m) cin >> b[i];

    ll t = 0;
    rep(i,m) t += b[i];
    int j = m;
    int ans = 0;
    rep(i,n+1) {
        while (j > 0 && t > k) {
            --j;
            t -= b[j];
        }
        if (t > k) break;
        ans = max(ans, i+j);
        if (i == n) break;
        t += a[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4824
# 解説AC
n = int(input())
mod = 10**9+7

# -----------DP解法----------
# ---考え方---
# 文字列として入ってはいけないものは、以下の5通り
# 'AGC', 'ACG', 'GAC', 'A?GC', 'AG?C'
# i文字目の決定に関与するのは、i-1, i-2, i-3文字目のみ

# 参考: https://drken1215.hatenablog.com/entry/2019/04/23/120400
# DP[i][i-3文字目:x][i-2文字目:y][i-1文字目:z] = 条件を満たす長さiの文字列の総数
# 以下、i文字目をmで表す

# 文字管理として、初期値:0, A:1, G:2, C:3, T:4とする
# (xyzm)として、(?123), (?132), (?213), (1?23), (12?3)が条件を満たさないパターン
# 


DP = [[[[0 for _ in range(5)] for _ in range(5)] for _ in range(5)] for _ in range(n+1)] 
DP[0][0][0][0] = 1

for i in range(n):
    # i-3~i-1文字目
    for x in range(5):
        for y in range(5):
            for z in range(5):
                # i文字目
                for m in range(1,5):
                    if y == 1 and z == 2 and m == 3:
                        continue
                    elif y == 1 and z == 3 and m == 2:
                        continue
                    elif y == 2 and z == 1 and m == 3:
                        continue
                    elif x == 1 and z == 2 and m == 3:
                        continue
                    elif x == 1 and y == 2 and m == 3:
                        continue
                    DP[i+1][y][z][m] = (DP[i+1][y][z][m] + DP[i][x][y][z]) % mod

ans = 0
for x in range(1,5):
    for y in range(1,5):
        for z in range(1,5):
            ans = (ans + DP[n][x][y][z]) % mod

print(ans)
                    

# -----------以下はメモ化再帰解法------------

# # 先に上記文字列が入っているかどうかを判定する関数を用意する
# # 入力されるsは4文字とする
# def moji_check(s):
#     if s.count('AGC') >= 1 or s.count('ACG') >= 1 or s.count('GAC') >= 1:
#         return False
#     elif s[0] == 'A' and s[2:4] == 'GC':
#         return False
#     elif s[:2] == 'AG' and s[3] == 'C':
#         return False
#     else:
#         return True

# # メモ化再帰で求める
# # memo[i]: 現在の文字数目に登場した
# memo = [{} for i in range(n+1)]

# def dfs(cur, s):
#     if s in memo[cur]:
#         return memo[cur][s]
#     if cur == n:
#         return 1
#     ret = 0
#     for c in 'AGCT':
#         if moji_check(s+c) == True:
#             ret = (ret + dfs(cur+1, s[1:] + c)) % mod
#     memo[cur][s] = ret
#     return ret
# print(dfs(0, 'TTT'))


Measured memory_bytes: 3572
import sys

# S = input()
# N, M = map(int, input().split())
# nums = list(map(int, input().split()))
# nums_2d = [list(map(int, input().split())) for _ in range(N)]


def main():

    x = int(input())

    n500 = x//500

    rest = x - 500 * n500

    n5 = rest // 5

    happy = n500 * 1000 + n5 * 5

    print(happy)


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    ll n,k,s,p,r;
    cin>>n>>k;
    cin>>s>>p>>r;
    string t;
    cin>>t;
    ll points=0;
    bool check[n];
    for(int i=0;i<n;i++)
    {
        check[i]=0;
    }
    for(int i=0;i<min(n,k);i++)
    {
        check[i]=1;
        if(t[i]=='s')
        {
            points+=s;
        }
        else if(t[i]=='p')
        {
            points+=p;
        }
        else
        {
            points+=r;
        }
    }
    for(int i=k;i<n;i++)
    {
        if(check[i-k])
        {
            if(t[i]!=t[i-k])
            {
                check[i]=1;
                if(t[i]=='s')
                {
                    points+=s;
                }
                else if(t[i]=='p')
                {
                    points+=p;
                }
                else
                {
                    points+=r;
                }
            }
        }
        else
        {
            check[i]=1;
            if(t[i]=='s')
            {
               points+=s;
            }
            else if(t[i]=='p')
            {
                points+=p;
            }
            else
            {
                points+=r;
            }
        }
    }
    cout<<points<<endl;
    return 0;
}


Measured memory_bytes: 512