akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    N = Scanner.int()
    if N % 2 == 1:
        print(0)
        return
    ans = 0
    while N > 0:
        ans += N // 10
        N //= 5
    print(ans)


def main():
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()


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

signed main() {

  int N; cin >> N;
  vector<long long> A(N);
  for (int i = 0; i < N; ++i) cin >> A[i];

  long long res = 0;
  for (int k = 0; k < 1e6; ++k) {
    for (int i = 0; i < N; ++i) {
      if (A[i] < N) continue;         // 操作の必要なし
      long long cnt = A[i] / N;
      A[i] %= N;
      for (int j = 0; j < N; ++j) {
        if (i == j) continue;
        A[j] += cnt;
      }
      res += cnt;
    }
  }

  cout << res << endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(a,b) for(int a=0;a<b;a++)
#define Sort(a) sort(a.begin(),a.end())
#define rev(a) reverse(a.begin(),a.end())
#define fi first
#define se second
#define co(a) cout<<a<<endl
#define sz size()
#define bgn begin()
#define en end()
#define pb(a) push_back(a)
#define pp() pop_back()
#define V vector
#define P pair
#define V2(a,b,c) V<V<int>> a(b,V<int>(c))
#define V2a(a,b,c,d) V<V<int>> a(b,V<int>(c,d))
#define incin(a) int a; cin>>a
#define yuko(a) setprecision(a)
#define uni(a) a.erase(unique(a.begin(),a.end()),a.end())
//#define min min<int>
//#define max max<int>
template<class T>
 void cou(vector<vector<T>> a){
  int b=a.size();
  int c=a[0].size();
  fo(i,b){
    fo(j,c){
      cout<<a[i][j];
      if(j==c-1)
        cout<<endl;
      else
        cout<<' ';
    }
  }
}
/*template<>
 void cou(vector<vector<char>> a){
  int b=a.size();
  int c=a[0].size();
  fo(i,b){
    fo(j,c){
      cout<<a[i][j];
      if(j==c-1)
        cout<<endl;
      else
        cout<<' ';
    }
  }
}*/
 int wari(int a,int b) {
   if(a%b==0)
     return a/b;
   else
     return a/b+1;
 }
 int keta(int a){
  double b=a;
  b=log10(b);
  int c=b;
  return c+1;
 }
 int souwa(int a){
  return a*(a+1)/2;
 }
 /*int lcm(int a,int b){
  int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return d*e/f;
    }
  int gcm(int a,int b){
      int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return f;
  }*/
 bool prime(int a){
   if(a<2)
     return false;
   else if(a==2)
     return true;
   else if(a%2==0)
     return false;
   double b=sqrt(a);
    for(int i=3;i<=b;i+=2){
      if(a%i==0){
        return false;
      }
    }
   return true;
 }
struct Union{
  vector<int> par;
  Union(int a){
	par= vector<int>(a,-1);
  }
  int find(int a){
    if(par[a]<0)
      return a;
    else
      return par[a]=find(par[a]);
  }
  bool same(int a,int b){
    return find(a)==find(b);
  }
  int Size(int a){
    return -par[find(a)];
  }
  void unite(int a,int b){
    a=find(a);
    b=find(b);
    if(a==b)
      return;
    if(Size(b)>Size(a))
      swap<int>(a,b);
    par[a]+=par[b];
    par[b]=a;
  }
};
int ketas(int a){
  string b=to_string(a);
  int c=0;
  fo(i,keta(a)){
    c+=b[i]-'0';
  }
  return c;
}
int gcm(int a,int b){
    if(b==0)
        return a;
    return gcm(b,a%b);
}
int lcm(int a,int b){
    return a/gcm(a,b)*b;
}
/*struct aa{
	vector<int> gt;
  aa(int n){
	gt= vector<int>(n, 1);
  }
	void c(V<int> d,int b){
	if(d[b]==0){
		gt[d[b]-1]++;
		gt[gt.sz-1]++;
	}
	else{
		gt[d[b]-1]++;
		c(d,d[d[b]]-1);
	}
}
void cok(int a){
	cout<<gt[a-1]<<endl;
	fo(i,a-1)
	cout<<gt[i]<<endl;
}
};
*/
/*struct dfs(){

}*/
signed main(){
  int a;
  cin>>a;
  V<int> b(a);
  fo(i,a){
    cin>>b[i];
  }
  Sort(b);
  int c=0;
  fo(i,a-1){
    c+=b[i];
  }
  if(c>b[a-1])
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
}

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

#define TCLOOP() int tc; cin>>tc; while(tc--)

#define fa(x,v) for(auto x:v)
#define f(i,a,b) for(ll i=(ll)a;i<=(ll)b;i++)
#define rf(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define spc " "
#define endl '\n'
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define len(s) int(s.length())
#define sz(v) int(v.size())
#define MOD 1000000007

// Code Here

ll n;
ll T,A;
vector < vector<ll> > adj;
vector <ll> parent;
vector <ll> path;

void dfs(ll u, ll p)
{
	parent[u] = p;
	if(u == T) {
		path.pb(T);
		return;
	}
	path.pb(u);
	f(i,0,sz(adj[u])-1) if(adj[u][i] != p) dfs(adj[u][i],u);
	if(path[sz(path)-1] == u) path.pop_back();
}

ll maxx = 0;

void dep(ll u, ll p, ll h)
{
	maxx = max(maxx,h);
	f(i,0,sz(adj[u])-1) if(adj[u][i] != p) dep(adj[u][i],u,h+1);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>T>>A; T--; A--;
    adj.resize(n);
    f(i,0,n-1) parent.pb(i);
    f(i,1,n-1) {
    	ll x,y; cin>>x>>y;
    	x--; y--;
    	adj[x].pb(y);
    	adj[y].pb(x);
    }
    dfs(A,A);
    ll d, tar;
    if(sz(path) % 2) tar = path[sz(path)/2+1], d = sz(path)/2+1;
    else tar = path[sz(path)/2], d = sz(path)/2;
    dep(tar,parent[tar],0);
    cout<<max((ll)0,maxx+d-1);
    return 0;
}

Measured memory_bytes: 11252
#include<stdio.h>
#include<stdlib.h>

int main() {
	int a, b, ans = 0;
	scanf("%d %d", &a, &b);
	for (int i = 0; i < 2; i++) {
		if (a > b) {
			ans += a;
			a--;
		}
		else {
			ans += b;
			b--;
		}
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 128
import java.util.*;
import java.math.*;

public class Main {
    static final int MOD = 1_000_000_007; // 10^9+7
    // static final int MAX = 2_147_483_646; // intの最大値
    static final int INF = 1_000_000_000; // 10^9
    static final int MAX = 10_000_000;
    static long[] fact = new long[100];
        public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        
        long n = sc.nextLong();
        long sum = 100;
        for(int i = 0;i < 4000;i++){
            if(n <= sum){
                System.out.println(i);
                return;
            }
            sum += sum/100;
        }
    }
    
}


Measured memory_bytes: 35872
import collections

n, m = map(int, input().split())
a = list(map(int, input().split()))
ac = collections.Counter(a)
for i in range(m):
    b, c = map(int, input().split())
    ac[c] += b
ac = sorted(ac.items(), reverse=True)
ans = 0
for i in ac:
    use = min(n, i[1])
    ans += i[0] * use
    n -= use
    if n == 0:
        break
print(ans)

Measured memory_bytes: 40992
N = int(input())
x = [list(map(int, input().split())) for _ in range(N)]
ax, ay = x[0][0], x[0][1]
bx, by = x[0][0], x[0][1]
cx, cy = x[0][0], x[0][1]
dx, dy = x[0][0], x[0][1]
for i in range(N):
    if abs(x[i][0] - 1) + abs(x[i][1] - 10**9) < abs(ax - 1) + abs(ay - 10**9):
        ax = x[i][0]
        ay = x[i][1]
    if abs(x[i][0] - 10**9) + abs(x[i][1] - 10**9) < abs(bx - 10**9) + abs(by - 10**9):
        bx = x[i][0]
        by = x[i][1]
    if abs(x[i][0] - 1) + abs(x[i][1] - 1) < abs(cx - 1) + abs(cy - 1):
        cx = x[i][0]
        cy = x[i][1]
    if abs(x[i][0] - 10**9) + abs(x[i][1] - 1) < abs(dx - 10**9) + abs(dy - 1):
        dx = x[i][0]
        dy = x[i][1]
print(max(abs(ax-dx)+abs(ay-dy), abs(bx-cx)+abs(by-cy)))


Measured memory_bytes: 107348
#include <stdio.h>
#define _USE_MATH_DEFINES
#include <math.h>

int main(void) {
	
	int n, m, sum=0, ans;
	int a[100001];

	scanf("%d %d", &n, &m);

	for (int i = 1; i <= m; i++)scanf("%d", &a[i]);

	for (int i = 1; i <= m; i++)sum += a[i];

	if (n < sum)printf("-1");
	else printf("%d", n - sum);

	return 0;
}

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

char a[22][22];

int n,m;
struct pos{
	int x;
	int y;
	int step;
};

pos make_pos(int a,int b,int c){
	pos ret;
	ret.x=a;
	ret.y=b;
	ret.step=c;
	return ret;
}
int bfs(int sx,int sy,int ex,int ey){
	bool vis[n+2][m+2];
	
	for(int i=0;i<=n+1;++i)
		for(int j=0;j<=m+1;++j)
			if(a[i][j]=='#')
				vis[i][j]=true;
			else
				vis[i][j]=false;
	
	queue<pos> q;
	q.push(make_pos(sx,sy,0));
	vis[sx][sy]=true;
	int move[2][4]={{0,0,-1,1},{-1,1,0,0}};
	
	while(!q.empty()){
		pos fr=q.front();
		q.pop();
		if(fr.x==ex&&fr.y==ey)
			return fr.step;
		pos newpo;
		for(int i=0;i<4;++i){
			int nx=fr.x+move[0][i];
			int ny=fr.y+move[1][i];
			if(vis[nx][ny])
				continue;
			vis[nx][ny]=true;
			newpo=make_pos(nx,ny,fr.step+1);
			q.push(newpo);
		}
	}
	return 0;
}

int main(){
	for(int i=0;i<22;++i)
		for(int j=0;j<22;++j)
			a[i][j]='#';
	cin>>n>>m;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			cin>>a[i][j];
	int maxv=0;
	for(int i1=1;i1<=n;++i1)
		for(int j1=1;j1<=m;++j1){
			if(a[i1][j1]=='#')
				continue;
			for(int i2=1;i2<=n;++i2)
				for(int j2=1;j2<=m;++j2){
					if(a[i2][j2]=='#')
						continue;
					if(i1==i2&&j1==j2)
						continue;
					maxv=max(maxv,bfs(i1,j1,i2,j2));
				}
		}
	
	cout<<maxv<<endl;
	return 0;
}

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

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

using namespace std;
using lint=long long;

const long long INF=1LL<<61;

int main(){
	int n; scanf("%d",&n);
	vector<lint> a(n);
	rep(i,n) scanf("%lld",&a[i]);

	vector<lint> dp1(n+1); // dp1[i] = ([0, i) について, i から始めて i で終わるときの最小コスト)
	vector<lint> dp3(n+1); // dp2[i] = ([0, i) について, i から始めて i より左で終わるときの最小コスト)
	vector<lint> dp2(n+1); // dp3[i] = ([i, n) について, i から始めて i で終わるときの最小コスト)
	vector<lint> dp4(n+1); // dp4[i] = ([i, n) について, i から始めて i より右で終わるときの最小コスト)
	lint sum=0;
	rep(i,n){
		sum+=a[i];
		dp1[i+1]=min(dp1[i]+(a[i]==0?2:a[i]%2),sum);
		dp2[i+1]=min(dp1[i],dp2[i])+(a[i]+1)%2;
	}
	sum=0;
	for(int i=n-1;i>=0;i--){
		sum+=a[i];
		dp3[i]=min(dp3[i+1]+(a[i]==0?2:a[i]%2),sum);
		dp4[i]=min(dp3[i+1],dp4[i+1])+(a[i]+1)%2;
	}

	lint ans=INF;
	rep(i,n+1) ans=min({ans,dp1[i]+dp3[i],dp1[i]+dp4[i],dp2[i]+dp3[i]});
	printf("%lld\n",ans);

	return 0;
}


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

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define MP make_pair
#define PB push_back
#define X first
#define Y second

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)((a).size())
#define FILL(a, value) memset(a, value, sizeof(a))
#define debug(a) cout << #a << " = " << a << endl;

const double PI = acos(-1.0);
const LL INF = 1e9 + 47;
const LL LINF = INF * INF;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int n;
	cin >> n;
	cout << 3 * n * n;
	
	cerr << "Time elapsed: " << clock() / (double)CLOCKS_PER_SEC << endl;
	return 0;
}



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

using namespace std;

int main() {
    int H, W;
    cin >> H >> W;

    int cnt = 0;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            char a;
            cin >> a;
            if (a == '#') cnt++;
        }
    }

    if (cnt == H + W - 1) {
        cout << "Possible" << endl;
    } else {
        cout << "Impossible" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <cstdlib>
#include <queue>
using namespace std;
struct node{
	int x,y,t;
};
int dx[10]={1,-1,0,0},dy[10]={0,0,1,-1},n,m,num;
char mp[110][110];
bool vis[110][110];
queue<node> q;
int bfs()
{
	q.push((node){1,1,1});
	while(!q.empty())
	{
		if(q.front().x==n&&q.front().y==m) return q.front().t;
		for(int i=0;i<4;i++)
		{
			int tx=q.front().x+dx[i],ty=q.front().y+dy[i];
			if(mp[tx][ty]=='.'&&!vis[tx][ty]) 
			{
				q.push((node){tx,ty,q.front().t+1});
				vis[tx][ty]=1;
			}
		}
		q.pop();
	}
	return -1;
}


int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n+1;i++)
	{
		for(int j=0;j<=m+1;j++)
		{
			mp[i][j]='#';
		}
	} 
	for(int i=1;i<=n;i++)
	{
		scanf("%s",mp[i]+1);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(mp[i][j]=='#') num++;
		}
	}
	int ans=bfs();
	if(ans==-1)
		printf("-1");	
	else
		printf("%d",n*m-num-bfs());
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl
#define debug cout << "hi" << endl

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int MOD = 1e9 + 7;
const int INF32 = 1<<30;
const ll INF64 = 1LL<<60;

int main()
{
	// #ifndef ONLINE_JUDGE
	// freopen(".in.txt", "r", stdin);
	// freopen(".out.txt", "w", stdout);
	// #endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, m; cin >> n >> m;
	priority_queue<ll> pq;
	ll ans = 0;
	for(int i = 0; i < n; i++)
	{
		ll a; cin >> a;
		ans += a;
		pq.push(a);
	}
	for(int i = 0; i < m; i++)
	{
		ll t = pq.top(); pq.pop();
		ans -= t/2 + (t & 1);
		pq.push(t/2);
	}
	cout << ans;

	return 0;
}

Measured memory_bytes: 1400
#include<bits/stdc++.h>
using namespace std;
int main(void) {
    long long n,m;
    cin >> n >> m;
    long long ans = 0LL;
    if (n>=2LL && m>=2LL) {
        ans = (n-2LL)*(m-2LL);
    }
    else if(n==1LL && m==1LL) {
        ans = 1LL;
    }
    else {
        ans = max(0LL, n-2LL) + max(0LL, m-2LL);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (D, G) = readIntList()
    val pc = (0 until D).map { readIntList() }

    fun f(sc: Int, n: Int, notAnsMax: Int, i: Int): Int {
        if (i == D) {
            if (G - sc > 0) {
                val nn = (G - sc - 1) / (notAnsMax + 1) / 100 + 1
                if (nn in 0 until pc[notAnsMax][0])
                    return n + nn
                return 9999
            } else {
                return n
            }
        }

        val (p, c) = pc[i]
        val a = f(sc + p * (i + 1) * 100 + c, n + p, notAnsMax, i + 1)
        val b = f(sc, n, i, i + 1)
        return Math.min(a, b)
    }

    println(f(0, 0, 0, 0))
}

fun readString() = readLine()!!
fun readInt() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readIntList() = readLine()!!.split(" ").map(String::toInt)

Measured memory_bytes: 37864
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int t = 0;
			
			
			if(a > b) {
				t = a;
				a = b;
				b = t;
			}
			
			if(b > c) {
				t = b;
				b = c;
				c = t;
			}
			
			if(a > b) {
				t = a;
				a = b;
				b = t;
			}
			System.out.println(a + " " + b + " " + c);
		
	}
}

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


int main() {
#ifdef HOME
    freopen("in", "r", stdin);
#endif

    int n;
    while (cin >> n) {
        ll a, b;
        cin >> a >> b;
        vector<int> v;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            v.push_back(x);
        }
        a -= b;

        int l = 0, r = 1e9;
        while (r - l > 1) {
            int m = (l + r) >> 1;

            ll cur = 0;
            for (int i = 0; i < n; i++) {
                ll rem = v[i] - 1LL * m * b;
                if (rem > 0) cur += (rem + a - 1) / a;

            }
            if (cur <= m) r = m;
            else l = m;
        }
        cout << r << endl;
    }

#ifdef HOME
    cerr << clock() / (double)CLOCKS_PER_SEC << endl;
#endif
    return 0;
}


Measured memory_bytes: 892
n=int(input())
a=list(map(int,input().split()))
ans=1
if min(a)==0:
    print(0)
    exit()
for i in a:
    ans*=i
    if ans>10**18:
        print(-1)
        exit()
if ans>10**18:
    print(-1)
    exit()
print(ans)

Measured memory_bytes: 84712
/*

*/
typedef long long ll;
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector> 
#include <queue>
#include <bitset>

using namespace std;


const int INF = 1e8;

// 状態を表すクラスpairの場合、typedefしておくと便利
typedef pair<int,int> point;

//入力 
const int MAX_H = 50, MAX_W = 50;
char maze[MAX_H][MAX_W]; // 迷路を表す文字列の配列
int H, W;
int sy, sx; // スタートの座標
int gy, gx; // ゴールの座標

int d[MAX_H][MAX_W]; // 各店までの最短距離の配列

// 移動4方向のベクトル
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

// (sy, sx)からの(gy, gx)への最短距離を求める
// たどり着けないとINF
int bfs(){
    queue<point> que;
	// 全ての点をINFで初期化
    for (int i = 0; i < H; ++i)
        for (int j = 0; j < W; ++j) d[i][j] = INF;
    // スタート地点をキューに入れ、その点の距離を0にする
    que.push(point(sy, sx));
    d[sy][sx] = 0;
 
	// キューが空になるまでループ
    while (que.size()){
    	// キューの先頭を取り出す
        point p = que.front(); que.pop();
        // 取り出してきた状態がゴールなら探索をやめる
        if (p.first == gy && p.second == gx) break;
 
		// 移動4方向をループ
        for (int i = 0; i < 4; ++i){
        	// 移動した後の点を(ny, nx)とする
            int ny = p.first + dy[i], nx = p.second + dx[i];
            
            // 移動が可能かの判定と既に訪れたことがあるかの判定
            // d[ny][nx]!=INFなら訪れたことがある
            if (0<=ny && ny<H && 0<=nx && nx<W
             && maze[ny][nx]!='#' && d[ny][nx]==INF){
                que.push(point(ny, nx));
                d[ny][nx] = d[p.first][p.second] + 1;
            }
        }
    }
    return d[gy][gx];
}


int main() {
	// 入力
    cin >> H >> W;
    sy = 0; sx = 0; gy = H-1; gx = W-1;
    for (int i = 0; i < H; ++i)
	    for (int j = 0; j < W; ++j) cin >> maze[i][j];
    
    //解法
    int num_white = 0;
    for (int i = 0; i < H; ++i)
	    for (int j = 0; j < W; ++j) if (maze[i][j]=='.') ++ num_white;

    int res = bfs();
    
    // 出力
    if (res==INF) printf("%d\n", -1);
    else printf("%d\n", num_white - res - 1);
}
 


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
long p[111111],a[111111],b[111111];
int compare(const void *c, const void *d) {
    return a[*(long*)c] - a[*(long*)d];
}
int main() {
    int n, m, c, b[111], a, ans = 0,i,j,sum;
    scanf("%d%d%d", &n, &m, &c);
    for (i = 0; i < m; i++)
        scanf("%d", &b[i]);
    for (i = 0; i < n; i++) {
        sum = c;
        for (j = 0; j < m; j++) {
            scanf("%d", &a);
            sum += a * b[j];
        }
        if (sum > 0)
            ans++;
    }
    printf("%d\n", ans);
    return 0;
}

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


int to_num(int k1, int k2) {
    int ret = 0;
    if (k1) ret+=2;
    if (k2) ret+=1;
    return ret;
}


int main() {
    int n, a, b, c; cin >> n >> a >> b >> c;
    vector<int> l(n); rep(i, n) cin >> l[i];
    int ans = 1001001001;

    rep (i, 1<<n) {
        rep (j, 1<<n) {
            // i, j 各桁の 1+1 ビットを用いて [0..4] を表現

            int a_ = 0;
            int b_ = 0;
            int c_ = 0;
            int syn = 0;

            rep (k, n) {
                int option = to_num(i>>k&1, j>>k&1);
                if (option == 0) {
                    if (a_ != 0) syn++;
                    a_ += l[k];
                }
                if (option == 1) {
                    if (b_ != 0) syn++;
                    b_ += l[k];
                }
                if (option == 2) {
                    if (c_ != 0) syn++;
                    c_ += l[k];
                }
            }

            // 無からは竹を作れない
            if (a_==0 || b_==0 || c_==0) continue;

            ans = min(ans, abs(a-a_)+abs(b-b_)+abs(c-c_)+10*syn);
        }
    }

    cout << ans << endl;
}

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

struct Eratos{
    vector<int> first_prime; //その数を割り切る最小の素数,その数自身のとき素数とわかる
    vector<int> P;

    Eratos(int N){
        first_prime.resize(N + 1);
        rep (i, N + 1)
            first_prime[i] = i;
        for(int i = 2; i <= N; i++){
            if(first_prime[i] == i){
                for(int j = 2 * i; j <= N; j += i){
                    first_prime[j] = min(first_prime[j], i);
                }
                P.pb(i);
            }
        }
    }
    vector<int> factorization(int n, vector<int> &f){
        if (n == 1)
            return f;
        else {
            f.pb(first_prime[n]);
            return factorization(n / first_prime[n], f);
        }
    }
};

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n)
        cin >> a[i];
    Eratos er(1000002);

    vector<int> s(1000002, 0);
    int judge1 = 1;
    int judge2 = 1;
    rep (i,n){
        vector<int> g;
        er.factorization(a[i], g);
        rep (j, g.size()){
            if (j == 0 || (j > 0 && g[j - 1] < g[j]))
                s[g[j]]++;
        }     
    }
    rep (i,1000002){
        if (s[i] > 1)
            judge1 = 0;
        if (s[i] == n)
            judge2 = 0;
    }
    if (judge1)
        cout << "pairwise coprime" << endl;
    else if (judge2)
        cout << "setwise coprime" << endl;
    else cout << "not coprime" << endl;
}


Measured memory_bytes: 15288
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,n) for(int i=0;i<n;i++)
template<class T> inline T gcd(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}else{return 0;}}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}else{return 0;}}

#define MOD 1000000007
typedef long long ll;

int main(){
  ll n,k;
  cin >> n >> k;
  ll a[1000000],b[1000000];
  vector<pair<ll,ll>> v; 
  FOR(i,n){
    cin >> a[i] >> b[i];
    v.push_back(make_pair(a[i],b[i]));
    
  }
  sort(v.begin(),v.end());
  ll sum=0;
  FOR(i,n){
    if(sum+v[i].second<k){
      sum+=v[i].second;
    }else{
      cout << v[i].first << endl;
      return 0;
    }
  }
  

  
}

Measured memory_bytes: 8052
#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define LL long long int
using namespace std;
const int N = 1e3 + 5;

int v[N], rem[N];
vector<int> g[N];
int main() {
    FASTIO;
    int n, i, j, nd;
    cin >> n;
    for (i=1;i<=n;i++) cin >> v[i];
    int nxt = 0, la = 0, done = 0;
    vector<int> ans;
    while(done < n) {
      la = 0;
      nxt = 0;
      for (i=1;i<=n;i++) if (!rem[i]) {
        nxt++;
        if (v[i] == nxt) {
          la = i;
        } 
      }
      if (la == 0) {
        cout << "-1\n";
        return 0;
      }
      rem[la] = 1;
      ans.push_back(v[la]);
      done++;
    }
    reverse(ans.begin(), ans.end());
    for (auto it : ans) cout << it << '\n';
    return 0;
}


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

using namespace std;

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

	string s,t;
	int res = 1e9;

	cin >> s;
	cin >> t;

	int n = s.length();
	int m = t.length();

	for(int i=0;i<=n-m;i++)
	{
		string sub = s.substr(i,m);
		int cnt = 0;
		for(int j=0;j<m;j++)
		{
			if(sub[j]!=t[j])
			{
				cnt++;
			}
		}
		res = min(res,cnt);
	}

	cout << res << '\n';
	
	return 0;	
}

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

const ll INF = 1LL << 60;

ll N;
vector<ll> t, x, y;
int main() {
    cin >> N;
    t.resize(N);
    x.resize(N);
    y.resize(N);

    rep(i, N) {
        cin >> t[i] >> x[i] >> y[i];
    }

    ll cur_x = 0, cur_y = 0, cur_t = 0;;

    bool ans = true;
    rep(i, N) {
        ll diff_x = abs(x[i] - cur_x), diff_y = abs(y[i] - cur_y), diff_t = t[i]- cur_t;
        if (diff_x + diff_y > diff_t) {
            ans = false;
            break;
        }

        // cout << i << " " << diff_t << " " << diff_x << " " << diff_y << endl;
        if (diff_t % 2 == (diff_x + diff_y) % 2) {
        } else {
            // cout << i << " p2" << endl;
            ans = false;
            break;
        }

        cur_x = x[i], cur_y = y[i], cur_t = t[i];
    }
    if (ans) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 5580
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
const int mod = 1000000007;
const int INF = 1001001001;
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(){
    int h,n;
    cin >> h >> n;
    vector<int> dp(h+1,INF);
    dp[0] = 0;
    rep(i,n){
        int a,b;
        cin >> a >> b;
        rep(j,h){
            int nj = min(j+a,h);
            chmin(dp[nj],dp[j]+b);
        }
    }
    cout << dp[h] << endl;
    return 0;
}

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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

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

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

signed main(void)
{
  int n;
  cin >> n;
  int sum = 0;
  REP(i, n) {
    int l, r;
    cin >> l >> r;
    sum += (r-l+1);
  }
  cout << sum << endl;

  return 0;
}


Measured memory_bytes: 256
import sys
def inpl(): return list(map(int, sys.stdin.readline().split()))

x = inpl()
N = []
cnt = 0
for i in range(0, x[0]):
    N.append(0)

for i in range(0, x[1]):
    tem = int(input())
    A = inpl()

    for j in range(0, tem):
        N[A[j]-1] += 1

for k in range(0, len(N)):
    if N[k] == 0:
        cnt += 1

print(cnt)

Measured memory_bytes: 67776
import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		try(Scanner scan = new Scanner(System.in);){
			int N = Integer.parseInt(scan.next());
			List<Integer> list = new ArrayList<Integer>();
			int count = 1;
			for(int i=0; i<N; i++) {
				list.add(Integer.parseInt(scan.next()));
                boolean flg = true;
				for(int j =0; j<list.size()-1;j++) {
					if(list.get(j) > list.get(list.size()-1)) {
						flg = false;
					}
					if(flg && j == list.size() -2) {
						count++;
					}
				}
			}
			System.out.println(count);
		}
	}
}


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

int main() {
    int N;
    cin >> N;
    vector<int> a(N);
    for(int i = 0; i < N; i++){
        cin >> a.at(i);
    }
    for(int i = 0; i < N - 1; i++){
        for(int j = i + 1; j < N; j++){
            if(a.at(i) < a.at(j)){
                int t = a.at(i);
                a.at(i) = a.at(j);
                a.at(j) = t;
            }
        }
    }
    int Alice = 0;
    int Bob = 0;
    for(int i = 0; i < N; i++){
        if(i % 2 == 0){
            Alice += a.at(i);
        }else{
            Bob += a.at(i);
        }
    }
    int dif = Alice - Bob;
    cout << dif << endl;
}

Measured memory_bytes: 3640
#include <iostream>
#include <vector>
using namespace std;
#pragma warning (disable: 4996)

int N, M, A[1 << 17], B[1 << 17], col[1 << 17], cnts; bool used[1 << 17];
vector<int> G1[1 << 17], G2[1 << 17], I;

void dfs1(int pos) {
	if (used[pos] == true) return;
	used[pos] = true;
	for (int i = 0; i < G1[pos].size(); i++) dfs1(G1[pos][i]);
	I.push_back(pos);
}

void dfs2(int pos) {
	if (col[pos] >= 1) return;
	col[pos] = cnts;
	for (int i = 0; i < G2[pos].size(); i++) dfs2(G2[pos][i]);
}

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= M; i++) {
		scanf("%d%d", &A[i], &B[i]);
		G1[A[i]].push_back(B[i]);
		G2[B[i]].push_back(A[i]);
	}
	for (int i = 0; i < N; i++) {
		if (used[i] == true) continue;
		dfs1(i);
	}
	for (int i = I.size() - 1; i >= 0; i--) {
		if (col[I[i]] >= 1) continue;
		cnts++; dfs2(I[i]);
	}
	int Q, A1, A2; scanf("%d", &Q);
	for (int i = 1; i <= Q; i++) {
		scanf("%d%d", &A1, &A2);
		if (col[A1] == col[A2]) printf("1\n");
		else printf("0\n");
	}
	return 0;
}


Measured memory_bytes: 10512
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#define ll long long
#define inf (1LL<<60)
using namespace std;
ll dp[3001][3001];
ll sum[3001][3001];
ll solve(vector<int> &v,int i,int j)
{
    if(i==j) return 0;
    if(dp[i][j]!=-1)
    {
        return dp[i][j];
    }
    ll minC=inf;
    for(int k=i;k<j;k++)
    {
        minC=min(minC,sum[i][j]+solve(v,i,k)+solve(v,k+1,j));
    }
    return dp[i][j]=minC;
}
void pre(vector<int> &v,int n)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            sum[i][j]=v[j]+((i==j)?0:sum[i][j-1]);
        }
    }
}
int main()
{
    int n;cin>>n;
    vector<int> v(n+1);
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    pre(v,n);
    cout<<solve(v,1,n);
    return 0;
}

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

int main() {
	int n, A[100];
	cin >> n;
	for (int i = 0; i < n; i++)cin>> A[i];
	
	for (int i = n - 1; i >= 0; i--) {
		if (i != n - 1)cout << " ";
		cout << A[i];
	}
	cout << endl;
	
	return 0;
}

Measured memory_bytes: 3080
#include<cstdio>
#include<iostream>
#include<queue>
#include<string>
#include<cmath>
#include<algorithm>
#include<limits.h>
#include<sstream>
#define rep(i,l,p) for(int i=l; i<=p; i++)
#define drep(i,p,l) for(int i=p; i>=l; i--)
using namespace std;


int main(){
	int ans;
	string s1,s2;
	cin >> s1 >> s2;
	s1 += s2;
	stringstream ss(s1);
	ss >> ans;
	int t = (int)(sqrt((double)ans));
	if ( t*t == ans) printf("Yes");
	else printf("No");
	return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main{
	public static void main(String[]args)throws IOException{
	
		BufferedReader br=
				new BufferedReader(new InputStreamReader(System.in));
		String str1=br.readLine();
		String[] str2 = str1.split(" ", 0);
	 
		int n1=Integer.parseInt(str2[0]);
		int n2=Integer.parseInt(str2[1]);
		int n3=Integer.parseInt(str2[2]);
		
		if(n1<=n3&&n3<=n2){
			System.out.println("Yes");
		}
		else{
			System.out.println("No");
		}
	}
	}

Measured memory_bytes: 22996
#include <bits/stdc++.h>
const long long MOD = 1000000007;
const int INF = INT_MAX / 2;
const long double PI = 3.1415926;
#define FOR(i, r, n) for(int i=(ll)(r); i<(ll)(n); i++)
#define REP(i, n) FOR(i, (0), n)
#define ALL(r) r.begin(), r.end()
#define ll long long int
using namespace std;
string s;
vector<ll> v;
vector<pair<ll, ll>> vp;
vector<vector<ll>> vv(110, vector<ll>(110, INF));
vector<tuple<ll, ll, ll>> vt;
set<ll> st;
map<char, ll> mp;

typedef int Weight;
struct Edge
{
	int from, to; Weight cost;
	bool operator < (const Edge& e) const { return cost < e.cost; }
	bool operator > (const Edge& e) const { return cost > e.cost; }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
void add_edge(Graph &g, int from, int to, Weight cost)
{
	g[from].push_back(Edge{ from, to, cost });
}

int main()
{
	string s;
	cin >> s;
	ll ans = 0, cnt = 0;
	REP(i,s.size())
	{
		if(s[i]=='g')
		{
			if(cnt)
			{
				cnt--;
				ans++;
			}
			else cnt++;
		}
		else
		{
			if (cnt) cnt--;
			else
			{
				cnt++;
				ans--;
			}
		}
	}
	cout << ans << endl;
}


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

#define ALL(a) (a).begin(), (a).end()
#define FOR(i, s, n) for (int i = (s); i < (n); i++)
#define rep(i, n) FOR(i, 0, n)
#define repi(i, n) FOR(i, 1, n + 1)
#define pp(v) cerr << #v "=" << (v) << endl;
#define ppa(v) cerr << "- " << #v << endl; rep(i,v.size()) cerr << #v << "[" << i << "] = " << v[i] << endl;
#define div_ceil(a,b) ((a) + ((b) - 1)) / (b)
#define UNIQUE(v) v.erase( unique(ALL(v)), v.end() );
#define INF 0x3f3f3f3f
#define LLINF 1000111000111000111LL
#define TIME system("date +%M:%S.%N")
using Graph = vector<vector<int>>;
using ll = long long;
template<class T> T gcd(const T &a, const T &b) { return a < b ? gcd(b, a) : b ? gcd(b, a % b) : a; }
template<class T> T lcm(const T &a, const T &b) { return a / gcd(a, b) * b; }

const int A = 0;
const int B = 1;
const int C = 2;

int main() {
  string s;cin>>s;
  int len = s.size();
  vector<char> ans;
  rep(i,len) {
    if (s[i]=='B') {
      if (ans.size()!=0) ans.pop_back();
    } else {
      ans.push_back(s[i]);
    }
  }
  rep(i,ans.size()) cout << ans[i];
  cout << endl;
}


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

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	int h, w, k;
	cin >> h >> w >> k;
	vector<string> cake(h);
	for(int i = 0; i < h; ++i){ cin >> cake[i]; }
	vector<int> vertical;
	vertical.push_back(0);
	for(int i = 0; i < h; ++i){
		bool found = false;
		for(int j = 0; j < w; ++j){
			if(cake[i][j] == '#'){ found = true; }
		}
		if(found){ vertical.push_back(i + 1); }
	}
	vertical.back() = h;
	vector<vector<int>> solution(h, vector<int>(w, -1));
	for(int r = 0, color = 1; r + 1 < vertical.size(); ++r){
		const int lo = vertical[r], hi = vertical[r + 1];
		vector<int> horizontal;
		horizontal.push_back(0);
		for(int j = 0; j < w; ++j){
			bool found = false;
			for(int i = lo; i < hi; ++i){
				if(cake[i][j] == '#'){ found = true; }
			}
			if(found){ horizontal.push_back(j + 1); }
		}
		horizontal.back() = w;
		for(int c = 0; c + 1 < horizontal.size(); ++c){
			const int lo2 = horizontal[c], hi2 = horizontal[c + 1];
			for(int i = lo; i < hi; ++i){
				for(int j = lo2; j < hi2; ++j){
					solution[i][j] = color;
				}
			}
			++color;
		}
	}
	for(const auto& v : solution){
		for(const auto& c : v){
			cout << c << " ";
		}
		cout << endl;
	}
	return 0;
}



Measured memory_bytes: 1280
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val N, M = sc.nextLong()
  val reverseCount =
    N match {
      case 1 => M match {
        case 1 => 1
        case _ => M - 2
      }
      case _ if M == 1 => N - 2
      case _ => (N - 2) * (M - 2)
    }
  println(reverseCount)
}


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


int main(){
    double a,b,c;
    scanf("%lf %lf %lf",&a,&b,&c);
    printf("%.7f\n",a*b*sin(M_PI*c/180)/2);
    printf("%.7f\n",a+b+sqrt(pow(a,2)+pow(b,2)-2*a*b*cos(M_PI*c/180)));
    printf("%.7f\n",b*sin(M_PI*c/180));
}


Measured memory_bytes: 3448
n,l=input().split(" ")
N=int(n)
L=int(l)
def sum(l,n):
    a=0
    for i in range (l,n+1):
        a+=i
    return a
def x(N,L):
    a=abs(L)
    b=1
    for i in range (1, N+1):
        if a>abs(L+i-1):
            b=i
            a=abs(L+i-1)
    return sum(L,L+N-1)-(L+b-1)
print (int(x(N,L)))

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

#define mod 1000000007
int sieve[1005],A[1005];

void precal()
{
	int i,j;
	sieve[1]=1;
	for (i=2;i*i<=1000;i++)
	{
		if(sieve[i])
		continue;
		
		for (j=2*i;j<=1000;j+=i)
		{
			if(sieve[j])
			sieve[j]=min(sieve[j],i);
			else sieve[j]=i;
		}
	}
	
	for (i=1;i<=1000;i++)
	{
		if(!sieve[i])
		sieve[i]=i;
	}
	
}

void fun(int N)
{
	while(N!=1)
	{
		A[sieve[N]]++;
		N/=sieve[N];
	}
}

int main()
{
	int N;
	
	precal();
	cin>>N;
	
	int i;
	for (i=2;i<=N;i++)
	{
		fun(i);
	}
	
	long long ans=1;
	
	//cout<<A[2];
	for (i=2;i<=N;i++)
	ans=(ans*(A[i]+1))%mod;
	
	cout<<ans;
	
	
}

Measured memory_bytes: 256
a,b,c,d,e,f = map(int,input().split())
dins = -1
suger = 0
ans = 0

for i in range(f//(a*100)+1):
  for j in range(f//(b*100)+1):
    if 100*(i*a+j*b)>f:
      continue
    else:
      water = 100*(i*a+j*b) 
      maxsuger = e*(i*a+j*b)
      for k in range(maxsuger//c+1):
        for l in range(maxsuger//d+1):
          su = k*c+l*d
          if su>maxsuger or (water+su)>f:
            continue
          else:
            if (water+su) != 0:
                nowd = (su/(water+su))*100
                if nowd>dins:
                  suger = su
                  ans = (water+su)
                  dins = nowd
print(ans,suger)
      

Measured memory_bytes: 73384
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define deb(a,b,c) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<", "<<#c<<" = "<<(c)<<endl;

typedef long long int ll;
typedef string str;

ll gcd(ll a, ll b){ 
    if (a == 0) 
        return b;  
    return gcd(b % a, a);
}

void fast(){
	ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main ()
{
	ll t,n,m,k,i,a,b,j;
	str s;
	cin >> s;
	if(s[0]==s[1] && s[1]==s[2] && s[2]=='R')
		cout << "3\n";
	else if((s[0]==s[1] && s[1]=='R') || (s[1]==s[2] && s[1]=='R' ))
		cout << "2\n";
	else if(s[0]=='R' || s[1]=='R' || s[2]=='R')
		cout << "1\n";
	else
		cout << "0\n";
	return 0;
}

Measured memory_bytes: 3592
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
typedef long long LL;

using namespace std;

int main()
{
	int a,b;
	cin >> a;
	b = a%10;
	
	switch(b)
	{
		case 2:
		case 4:
		case 5:
		case 7:
		case 9:
			cout << "hon" << endl;
			break;
		case 0:
		case 1:
		case 6:
		case 8:
			cout << "pon" << endl;
			break;
		case 3:
			cout << "bon" << endl;
			break;
	}
	return 0;
} 

Measured memory_bytes: 3592
//atcoder beginer contest 144 B

#include <stdio.h>
int main(){
 int i;
 int m;
 int flag=0;
 scanf("%d",&m);
 for (i=1;i<=9;i++){
  if(m/i<=9&&m%i==0){
   flag++;
   break;
  }
 }
 if(flag==1) printf("Yes");
 else printf("No");
 return 0;
}


Measured memory_bytes: 128
#pragma GCC optimize ("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse4")
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
#define all(x) x.begin(), x.end()
#define trav(i,a) for(auto &i:a) 
inline int in(){int x;scanf("%lld",&x);return x;}
int cnt[100][100];
int32_t main()
{
	int n=in();
	int ans=0;
	for(int j=0;j<n;j++)
	{
		double x;
		cin>>x;
		int i=llround(x*1e9);
		int t=0,f=0;
		//cout<<i<<"\n";
		while(i%2==0)t++,i/=2;
		while(i%5==0)f++,i/=5;
		for(int x=max(18-t,0LL);x<70;x++)
		for(int y=max(18-f,0LL);y<70;y++)
		ans+=cnt[x][y];
		
		cnt[t][f]++;
	}
	cout<<ans;
	
}


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

using namespace std;

const int N = 1e5 + 1;
int n, m;
struct elm {
	int a, b;
} a[N];	
bool operator<(const elm& l, const elm& r) { return l.a < r.a || (l.a == r.a && l.b > r.b); }

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i)
		scanf("%d%d", &a[i].a, &a[i].b);
	typedef long long ll;
	ll res = 0;
	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= n && m > 0; ++i) {
		int mm = min(m, a[i].b);
		res += 1LL * mm * a[i].a;
		m -= mm;
	}
	printf("%lld", res);
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, t, s;
int a[3005] = { 0 };
int b[3005] = { 0 };
int dp[3005][3005] = { 0 }, dp2[3005][3005] = { 0 };
int main() {
	cin >> n >> t >> s;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= t; j++) {
			if (i == 0) {
				if (j - b[i] >= 0) dp[i][j] = a[i];
			}
			else {
				if (j - b[i]<0) {
					dp[i][j] = dp[i - 1][j];
				}
				else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - b[i]] + a[i]);
			}
		}
	}
	for (int i = n-1; i >= 0; i--) {
		for (int j = 0; j <= t; j++) {
			if (i == n-1) {
				if (j - b[i] >= 0) dp2[i][j] = a[i];
			}
			else {
				if (j - b[i]<0) {
					dp2[i][j] = dp2[i + 1][j];
				}
				else dp2[i][j] = max(dp2[i + 1][j], dp2[i + 1][j - b[i]] + a[i]);
			}
		}
	}
	int res = 0;
	for (int i = 0; i < n; i++) {
		int sum = 0;
		sum += dp[i][s];
		if (i != n - 1) sum += dp2[i + 1][t - s];
		res = max(res, sum);
	}
	cout << res << endl;
	return 0;
}


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

#define fr(i,n) _back
#define pb	push_back
#define eb	emplace_back
#define mk	make_pair
#define fi	first
#define se	second
#define endl	'\n'

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);

int main() {
    ios_base::sync_with_stdio(false);
    int n,m; cin >> n >> m;
    vector<int> in(n,0);
    vector<int> ans(n,0);
    vector<vector<int>> g(n,vector<int>());

    while(m--) {
        int x,y; cin >> x >> y;
        x--;y--;
        g[y].pb(x);
        in[x]++;
    }

    queue<int> edges;
    for(int i = 0; i < n; i++)
        if(!in[i]) edges.push(i);

    int best = 0;

    while(!edges.empty()) {
        int u = edges.front();
        edges.pop();
        best = max(best,ans[u]);
        for(int v : g[u]) {
            in[v]--;
            ans[v] = max(ans[v], ans[u]+1);
            if(!in[v]) edges.push(v);
        }
    }

    cout << best << endl;

    return 0;
}



Measured memory_bytes: 6528
import java.util.*;
public class Main{
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[] A = new int[N];
		int i;
		int sum = 0;
		String ans = "Yes";
		double judge;
		for(i = 0;i < N;i++){
			A[i] = sc.nextInt();
			sum += A[i];
		}
		Arrays.sort(A);
		for(i = 0;i < M;i++){
			if(A[N - 1 - i] * (4 * M) < sum){
				ans = "No";
			}
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 23764
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<deque>
#include<functional>
#include<ctime>
#include<cassert>
#include<cstring>
#include<unordered_map>
using namespace std;

#define sz(x) (int)(x.size())
#define fi(a,b) for(int i=a;i<=b;++i)
#define fj(a,b) for(int j=a;j<=b;++j)
#define fo(a,b) for(int o=a;o<=b;++o)
#define fdi(a,b) for(int i=a;i>=b;--i)
#define fdj(a,b) for(int j=a;j>=b;--j)
#define fdo(a,b) for(int o=a;o>=b;--o)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef double ld;
typedef vector<int> vi;

template<class T> bool uin(T &a, T b){ return (a > b ? a = b, true : false); }
template<class T> bool uax(T &a, T b){ return (a < b ? a = b, true : false); }

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

int const MAXN = 341;

int d[MAXN][MAXN][MAXN];
char s[MAXN];
int k;
int n;
int ans;

int rec(int l, int r, int k) {
	if (l > r) {
		return 0;
	}
	if (l == r) {
		return 1;
	}
	if (d[l][r][k] != -1) {
		return d[l][r][k];
	}
	int res = 0;
	if (k) {
		uax(res, 2 + rec(l + 1, r - 1, k - 1));
	}
	if (s[l] == s[r]) {
		uax(res, 2 + rec(l + 1, r - 1, k));
	}
	uax(res, rec(l + 1, r, k));
	uax(res, rec(l, r - 1, k));
	d[l][r][k] = res;
	return res;
}

void solve(){
	memset(d, 255, sizeof(d));
	n = strlen(s);
	ans = rec(0, n - 1, k);	  
}

int main(){
#ifdef LOCAL
	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
#endif

	scanf("%s", s);
	scanf("%d", &k);	
	solve();		
	printf("%d\n", ans);
	
#ifdef LOCAL
	fprintf(stderr, "ELAPSED TIME: %.3lf\n", (ld) clock() / CLOCKS_PER_SEC);
#endif	
	
	return 0;
}

Measured memory_bytes: 155136
N, K = map(int, input().split())
S = input()
RLE = []
now_char = S[0]
cnt = 1
for i in range(1, N):
    if S[i] == now_char:
        cnt += 1
    else:
        RLE.append([now_char, cnt])
        now_char = S[i]
        cnt = 1
RLE.append([now_char, cnt])

n = len(RLE)
if n//2 <= K:
    print(N-1)
    exit()
print(N - n + 2 * K)

Measured memory_bytes: 13300
#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
#include<cstdio>
using ll = long long;
using namespace std;
int main(){
    int n,k;
    cin >> n >> k;
    if(n%k==0)  cout << 0 << endl;
    else       cout << 1 << endl;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
P = list(map(int,input().split()))

ans = 0
A = [0,0,0]
for i in range(1, n-1):
    A = [P[i-1],P[i],P[i+1]]
    A.sort()
    if A[1] == P[i]:
        ans += 1

print(ans)


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

int main(){
	ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	string s;cin>>s;
	string k=s;
	reverse(k.begin(),k.end());
	if(k!=s){
		cout<<"No";
		return 0;
	}
	string l="",p="";
	for(Long i=0;i<(s.size()-1)/2;i++){
		l=l+s[i];
		p=s[i]+p;
	}
	if(l!=p){
		cout<<"No";
		return 0;
	}
	string m="",q="";
	for(Long i=(s.size()+1)/2;i<s.size();i++){
		m=m+s[i];
		q=s[i]+q;
	}
	if(q!=m){
		cout<<"No";
		return 0;
	}
	
	cout<<"Yes";
}

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

namespace _1_9_a
{
    class Program
    {
        static void Main(string[] args)
        {
            string word = Console.ReadLine();
            string txt = "";
            string[] text;
            int Count = 0;
            //List<string> text1 = new List<string>();
            while ((txt = Console.ReadLine()) != "END_OF_TEXT")
            {
                text = txt.ToLower().Split(' ');

                for (int i = 0; i < text.Length; i++)
                {
                    string t = text[i];
                    if (t == word)
                    {
                        Count += 1;
                    }
                }
            }
            Console.WriteLine("{0}",Count);
            Console.ReadKey();
        }
    }
}



Measured memory_bytes: 17836