akhauriyash/Code-Regression huggingface dataset:
import sys


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instr = lambda: sys.stdin.readline()
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

n, m = inintm()
X = inintl()

X.sort()
diff = []

if n >= m:
    print(0)
    exit()

for i in range(m-1):
    diff.append(X[i+1] - X[i])

diff.sort()

print(sum(diff[:m-n]))


Measured memory_bytes: 90880
//おまじない
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define INF 1e9+7
#define roop(i,m,n) for(int i=m;i<n;i++)
#define mroop(i,m,n) for(int i=m;i<n;i--)
#define NO cout<<"NO"<<endl;
#define YES cout << "YES"<<endl;
#define No cout << "No"<<endl;
#define Yes cout << "Yes"<<endl;
using namespace std;
typedef long long int ll;

//おまじない



int main() {

	int n,k, x, y;
	cin >>n>> k >> x >> y;

	if (n <= k) {
		cout << x * n << endl;
	}
	else {
		cout << x * k + y * (n - k) << endl;
	}


	return 0;
}

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

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

ll lcm(ll a, ll b)
{
  return a * b / gcd(a, b);
}

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

  cout << lcm(a, b);

}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define rep2(i,j,n) for(int j=i;j<n;j++)
#define rep3(i,j,n) for(int j=i;j<=n;j++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define sp(n) cout << fixed << setprecision(n)
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; }
typedef long long ll;
using namespace std;
const ll mod=1e+9+7;
int main(void){
    ll n,k;cin>>n>>k;
    vector<vector<ll>> t(n),tt(n);
    rep(i,n-1){
        int a,b;cin>>a>>b;a--;b--;
        t[a].push_back(b);
        t[b].push_back(a);
    }
    queue<ll> que;
    que.push(0);
    ll res=1;
    vector<bool> used(n,false);
    while(que.size()){
        int x=que.front();que.pop();
        used[x]=true;
        ll now=k;
        tt[x].push_back(x);
        rep(i,t[x].size()){
            int y=t[x][i];
            if(used[y]) now-=tt[y].size();
            else que.push(y);
            tt[y].push_back(x);
        }
        res*=now;
        res%=mod;
        //cout<<res<<endl;
    }
    cout<<res<<endl;
}

Measured memory_bytes: 14324
#include<stdio.h>
int main()
{ int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    if(a<b && a<c && b<c){
        printf("Yes\n");
        
    }
    else{
        printf("No\n");
        
    }
    return 0;
    
}


Measured memory_bytes: 2112
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
#define N 1001
#define MAX 10001
 
#define min(x,y) ( (x) < (y) ? (x) : (y) )
 
int compare (const void* a, const void* b) {
  return *(int*)a - *(int*)b;
}
 
int main () {
  int n;
  int array[N];
  int sortedArray[N];
   
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &array[i]);
    sortedArray[i] = array[i];
  }
  qsort(sortedArray, n, sizeof(int), compare);
  int gMin = sortedArray[0];
 
  int index[MAX];
  for (int i = 0; i < n; i++) {
    index[sortedArray[i]] = i;
  }
 
  bool isUsed[N];  
  for (int i = 0; i < n; i++) {
    isUsed[i] = false;
  }
 
  int totalCost = 0;
  for (int i = 0; i < n; i++) {
    if (isUsed[i]) {
      continue;
    }
 
    int cycleSum  = 0;
    int cycleCard = 0;
    int cycleMin  = MAX;
    int pos = i;
    while (1) {
      isUsed[pos] = true;
 
      cycleCard++;      
      cycleSum += array[pos];
      cycleMin  = min(cycleMin, array[pos]);
 
      pos = index[array[pos]];
 
      if (isUsed[pos]) {
    break;
      }
    }
 
    if ( 2*(cycleMin + gMin) < (cycleCard - 1)*(cycleMin - gMin) ) {
      totalCost += cycleSum + cycleMin + (cycleCard + 1)*gMin;
    } else {
      totalCost += cycleSum + (cycleCard - 2)*cycleMin;
    }
  }
 
  printf("%d\n", totalCost);
   
  return 0;
}


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

int main(){
    string S,T;
    cin >> S >> T;
    for (int i = 0; i < S.size(); i++) {
        if (S.at(i) != T.at(i)) {
            cout << "No" << endl;
            return 0;
        } 
    }
    cout << "Yes" << endl;
}


Measured memory_bytes: 3600
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#define ll long long
using namespace std;
int main(){
	int K,S;
	cin>>K>>S;
	int sum=0;
	for(int i=0;i<=K;i++){
		ans:
		for(int j=0;j<=K;j++){
				if(S-i-j>=0 && S-i-j<=K){
					sum++;
				}	
			
		}
	}
	cout<<sum<<endl;
	return 0;
} 

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

int main() 
{
    int n, m=0;
    cin >> n;
    vector<int> v(n);
    for (int i=0; i<n; i++)
        cin >> v[i];
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            m = max(abs(v[i]-v[j]),m);
    cout << m;
    return 0;
}

Measured memory_bytes: 256
import networkx as nx

N, M = map(int, input().split())
S = [list(input()) for i in range(N)]
G = nx.DiGraph() # 有向グラフ
G.add_nodes_from(['S', 'T']) # 'S' -> 'T'のflowを考える

# (i+j)の偶奇でグループ分け
# 偶数のマスは奇数のマスと隣接しており、奇数のますは偶数のマスと隣接している
for i in range(N):
    for j in range(M):
        if S[i][j] == '#':
            continue
        if (i + j) % 2 == 0:
            G.add_edge('S', (i, j), capacity=1) # 偶数のマスは'S'と繋ぐ
            # 隣接する奇数のマスが空なら辺を追加('S' -> 'T'の向きで)
            for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                ii = i+di; jj = j+dj
                if 0<=ii<N and 0<=jj<M and S[ii][jj]=='.':
                    G.add_edge((i, j), (ii, jj), capacity=1)
        else:
            G.add_edge((i, j), 'T', capacity=1) # 奇数のマスは'T'と繋ぐ

max_flow, flow = nx.maximum_flow(G, 'S', 'T')
for s in flow:
    if s in {'S', 'T'}:
        continue

    i, j = s
    for t in flow[s]:
        if t == 'T':
            continue

        ii, jj = t
        f = flow[s][t]
        if f:
            if ii == i+1:
                S[i][j] = 'v'; S[ii][jj] = '^'
            elif ii == i-1:
                S[i][j] = '^'; S[ii][jj] = 'v'
            elif jj == j+1:
                S[i][j] = '>'; S[ii][jj] = '<'
            else:
                S[i][j] = '<'; S[ii][jj] = '>'

print(max_flow)
for s in S:
    print(''.join(s))

Measured memory_bytes: 119252
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <limits>
#include <numeric>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <stack>

using namespace std;

#define INFint (1<<30)
#define BOUND 27182818284
#define MAT 2

typedef long long ll;
typedef long long int lli;
typedef pair<ll, ll> P;

ll MOD = 1000000007;
const ll INF = (1ll<<60);
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for(int i=int(a);i<int(b);++i)

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

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

// gcd
template<typename T>
T gcd(T a, T b) {
    if (a == 0)
        return b;
    return gcd(b % a, a);
}

int findGCD(vector<int> arr) {
    int result = arr[0];
    for (auto a: arr) {
        result = gcd(a, result);
    }
    return result;
}

template<typename T>
T lcm(T m, T n) {
    // 引数に0がある場合は0を返す
    if ((0 == m) || (0 == n))
        return 0;
    return ((m / gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
    fill((T *) array, (T *) (array + N), val);
}


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

// v.front() = -BOUND;
// v.back() = BOUND;

//struct edge{
//    int cost, to;
//
//    edge(int in_cost, int in_to){
//        cost=in_cost;
//        to=in_to;
//    }
//    bool operator<(const edge &a) const
//    {
//        return cost > a.cost;
//    }
//};

int main() {
    int N; cin >> N;
    double a=1;
    while(a<50010){
        if(floor(a*1.08) == N){
            cout << (int)a << endl;
            return 0;
        }
        a=a+1;
    }
    cout << ":(" << endl;
    return 0;
}


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

#define io ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define ll long long
#define ull unsigned long long
#define pii pair<ll, ll>
#define piii pair<ll, pair<ll, ll>>
#define debug(x) cout<<#x<<" = "<<x<<endl

using namespace std;
const int N = 200005;
ll t, n, m, k, q, a, b, x, y, ans, arr[N];
ll mod = 998244353;
string s;
bool vis[N];
map<ll, ll> cnt;

int main() {
    io;
    t = 1;
//    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> arr[i];
            ++cnt[i - arr[i]];
        }
        for (int i = 1; i <= n; ++i) {
            ans += cnt[i + arr[i]];
        }
        cout << ans << endl;
    }
    return 0;
}
//  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);


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

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

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

    vector<long long> sum(N - K + 1);
    long long ans1 = 0;
    long long ans2 = 0;
    for (int i = 0; i < N - K + 1; i++) {
        ans1 = abs(x[i]) + x[i + K - 1] - x[i];
        ans2 = abs(x[i + K - 1]) + x[i + K - 1] - x[i];
        sum[i] = min(ans1, ans2);
    }

    sort(sum.begin(), sum.end());
    cout << sum[0] << endl;
}

Measured memory_bytes: 1024
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Pranay2516
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(1, in, out);
        out.close();
    }

    static class Task {
        public void solve(int testNumber, FastReader in, PrintWriter out) {
            int a = in.nextInt(), b = in.nextInt(), c = in.nextInt(), k = in.nextInt();
            if (k <= a) out.println(k);
            else if (k <= a + b) out.println(a);
            else if (k <= a + b + c) out.println(a - (k - a - b));
        }

    }

    static class FastReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private FastReader.SpaceCharFilter filter;

        public FastReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {

            if (numChars == -1)
                throw new InputMismatchException();

            if (curChar >= numChars) {

                curChar = 0;

                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (numChars <= 0)
                    return -1;
            }

            return buf[curChar++];
        }

        public int nextInt() {

            int c = read();

            while (isSpaceChar(c))
                c = read();

            int sgn = 1;

            if (c == '-') {
                sgn = -1;
                c = read();
            }

            int res = 0;

            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();

                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));

            return res * sgn;
        }

        public boolean isSpaceChar(int c) {

            if (filter != null)
                return filter.isSpaceChar(c);

            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}



Measured memory_bytes: 32468
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 3e3 + 5;
int l1, l2;
string A, B;
int DP[MAXN][MAXN];


int rec(int s1, int s2)
{
    if(s1 == l1 || s2 == l2)
        return 0;
    if(DP[s1][s2] != -1)
        return DP[s1][s2];
    if(A[s1] == B[s2])
    {
        return DP[s1][s2] = max(1 + rec(s1 + 1, s2 + 1), max(rec(s1 + 1, s2), rec(s1, s2 + 1)));
    }
    else{
        return DP[s1][s2] = max(rec(s1 + 1, s2), rec(s1, s2 + 1));
    }
    return DP[s1][s2];
}

void print(int s1, int s2)
{
    if(s1 == l1 || s2 == l2)
        return;
    if(A[s1] == B[s2])
    {
        if((1 + DP[s1 + 1][s2 + 1]) >= DP[s1 + 1][s2] && (1 + DP[s1 + 1][s2 + 1]) >= DP[s1][s2 + 1])
        {
            cout << A[s1];
            print(s1 + 1, s2 + 1);
        }
        else if(DP[s1 + 1][s2] >= (1 + DP[s1 + 1][s2 + 1]) && DP[s1 + 1][s2] > DP[s1][s2 + 1])
        {
            print(s1 + 1, s2);
        }
        else{
            print(s1, s2 + 1);
        }
    }
    else{
        if(DP[s1 + 1][s2] > DP[s1][s2 + 1])
            print(s1 + 1, s2);
        else
            print(s1, s2 + 1);
    }
}

int main()
{
    cin >> A >> B;
    l1 = A.size();
    l2 = B.size();
    for(int i = 0; i < MAXN; ++i)
        for(int j = 0; j < MAXN; ++j)
            DP[i][j] = -1;
    rec(0, 0);
    print(0, 0);
    cout << endl;
    return 0;
}

Measured memory_bytes: 35968
import java.util.HashSet;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		int n = scan.nextInt();
		HashSet<String> present = new HashSet<String>();

		for(int i = 0;i < n;i++) {
			present.add(scan.next());

		}

		System.out.println(present.size());
	}
}

Measured memory_bytes: 77016
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef pair<int, int> P;
typedef long long ll;
int main(){
    int a,b,c;
    cin >> a >> b >> c;
    if(c<=a+b&& c>=a){
        cout << "YES" << endl;
    }
    else{
        cout << "NO" << endl;
    }
    return 0;
}

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

int n, x[100];

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> x[i];
    int mn = INT_MAX;
    for(int i = 0; i <= 100; i++){
	int sum = 0;
	for(int j = 0; j < n; j++) sum += (i - x[j]) * (i - x[j]);
	mn = min(mn, sum);
    }
    cout << mn << "\n";
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        while(true){
            
         int x = sc.nextInt();
         int y = sc.nextInt();
            
            if(x == 0 && y == 0){
                break;
            }
         if( x<y ){
             System.out.println(x+" "+y);
         }else{
             System.out.println(y+" "+x);
     	    }
        }
    }
}


Measured memory_bytes: 35880
n = gets.to_i

$visited = []
# $is_honest = Array.new(n, nil)
$as = []

n.times do
  ans = Array.new
  a = gets.to_i
  a.times do
    x, y = gets.split.map(&:to_i)
    ans << [x, y == 1]
  end
  $as << ans
end


res = 0
bitflag = 0
while bitflag <= 2 ** n
  is_honest = Array.new(n, nil)
  n.times do |i|
    flag = 2 ** i
    # p [bitflag, flag, i, flag & bitflag]
    is_honest[i] = (flag & bitflag) > 0 ? true : false
  end
  valid = true
  $as.each_with_index do |a, current|
    a.each do |i|
      idx = i[0] - 1
      target_is_honest = i[1]
      if is_honest[idx] != target_is_honest && is_honest[current]
        # p is_honest
        # puts "#{idx} != #{target_is_honest} (#{current} said)"
        valid = false
        break
      end
    end
    break unless valid
  end
  res = [is_honest.count(true), res].max if valid
  bitflag += 1
end

puts res


Measured memory_bytes: 1916
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(), k = in.nextInt();
		int minus = 0;
		int ideal = 0;
		int[] dq = new int[n];
		for ( int i = 0; i < n; i++ ) {
			int inp = in.nextInt();
			dq[i] = inp;
			if ( inp < 0 ) minus++;
			else ideal += inp;
		}
		in.close();

		// 全要素から自由に取捨選択できる場合
//		if ( n + minus <= k ) {
//			System.out.println(ideal);
//			return;
//		}

		int total = 0;
		for ( int l = 0; l < n; l++ ) {
			for ( int r = 0; r <= n - l; r++ ) {
				int lr = l + r;
				if ( lr > k || lr > n ) break;

				PriorityQueue<Integer> pool = new PriorityQueue<>();
				for ( int i = 0; i < l; i++ ) {
					pool.add(dq[i]);
				}
				for ( int i = n - 1; n - r <= i; i-- ) {
					pool.add(dq[i]);
				}
				
//				System.out.print("pool: ");
//				for ( Integer i : pool ) {
//					System.out.println(i);
//				}
				
				for ( int i = k - lr; 0 < i; i-- ) {
					if(!pool.isEmpty() && pool.peek() < 0) {
						pool.poll();
					}else {
						break;
					}
				}

				int temp = 0;
				for ( Integer i : pool ) {
					temp += i;
				}
				
//				System.out.println("l:" + l + " r:" + r + "   temp:" + temp );
				total = Math.max(total, temp);
			}
		}
		
		System.out.println(total);
	}
}

Measured memory_bytes: 26068
#include <bits/stdc++.h>
using namespace std;
#define MAX powl(10,18)+1
typedef long long ll;

int main(){
    int N;
    ll K;
    cin>>N>>K;
    vector<int> A(200001);
    for(int i=1;i<N+1;i++){
        cin>>A[i];
    };

    vector<int> s;
    vector<int> color(200001,-1);
    int x=1,i=0;
    while(1){
        if(color[x]==-1){
            s.push_back(x);
            color[x]=i++;            
            x=A[x];
        }
        else{
            break;
        }                
    }
    int loopsize=i-color[x];
    if(K<i){
        cout<<s[K]<<endl;
    }
    else{
        ll y=(K-color[x])%loopsize+color[x];
        cout<<s[y]<<endl;
    }    
}

Measured memory_bytes: 5888
package main

import "fmt"

func main() {
	var a, b, c int
	fmt.Scanf("%d %d %d", &a, &b, &c)
	if (a == b+c) || (b == a+c) || (c == a+b) {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 512
package main

import (
    "fmt"
)

func main() {
    var c1, c2, c3 string
    fmt.Scan(&c1, &c2, &c3)
    var c11 = string(c1[0])
    var c22 = string(c2[1])
    var c33 = string(c3[2])
    var ans = c11 + c22 + c33
    fmt.Println(ans)
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using ll = long long;
using P = pair<int, int>;
const int INF = 1e9;
const long long LINF = 1e18;
const long long MOD = 998244353;

template <int MOD = 1000000007>
struct Mint{
    int x;

    Mint() : x(0) {}
    Mint(long long t){
        x = t % MOD;
        if(x < 0) x += MOD;
    }
    
    Mint pow(int n){
        Mint res(1), t(x);
        while(n > 0){
            if(n & 1) res *= t;
            t *= t;
            n >>= 1;
        }
        return res;
    }

    Mint inv() const {
        int a = x, b = MOD, u = 1, v = 0, t;
        while(b > 0){
            t = a / b;
            a -= t * b;
            swap(a, b);
            u -= t * v;
            swap(u, v);
        }
        return Mint(u);
    }

    Mint & operator += (Mint a){
        x += a.x;
        if(x >= MOD) x -= MOD;
        return *this;
    }
    
    Mint & operator -= (Mint a){
        x += MOD - a.x;
        if(x >= MOD) x -= MOD;
        return *this;
    }

    Mint & operator *= (Mint a){
        x = int(1LL * x * a.x % MOD);
        return *this;
    }

    Mint & operator /= (Mint a){
        return (*this) *= a.inv();
    }

    Mint operator + (Mint a) const { return Mint(x) += a; }
    Mint operator - (Mint a) const { return Mint(x) -= a; }
    Mint operator * (Mint a) const { return Mint(x) *= a; }
    Mint operator / (Mint a) const { return Mint(x) /= a; }

    Mint operator - () const{ return Mint(-x); }

    bool operator == (const Mint a){ return x == a.x; }
    bool operator != (const Mint a){ return x != a.x; }
    bool operator < (const Mint a){ return x < a.x; }

    friend ostream & operator << (ostream & os, const Mint &a){
        return os << a.x;
    }

    friend istream & operator >> (istream & is, Mint &a){
        int t;
        is >> t;
        a = Mint<MOD>(t);
        return (is);
    }
};

signed main() {
    int n, s;
    cin >> n >> s;
    int a[n];
    rep(i,n){
        cin >> a[i];
    }
    Mint<MOD> dp[n + 1][s + 1][3];
    dp[0][0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= s;j++){
            dp[i + 1][j][0] += dp[i][j][0];
            dp[i + 1][j][1] += dp[i][j][0] + dp[i][j][1];
            dp[i + 1][j][2] += dp[i][j][0] + dp[i][j][1] + dp[i][j][2];
            if (j - a[i] < 0) continue;
            dp[i + 1][j][1] += dp[i][j - a[i]][0] + dp[i][j - a[i]][1];
            dp[i + 1][j][2] += dp[i][j - a[i]][0] + dp[i][j - a[i]][1];
        }
    }
    cout << dp[n][s][2] << endl;
    return 0;
}

Measured memory_bytes: 105856
#include <bits/stdc++.h>
using namespace std; 
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ll long long
long long min(long long x,long long y){return (x<y ? x:y);}
long long max(long long x,long long y){return (x>y ? x:y);}
#define ld long double
int stoi(string s) {return atoi(s.c_str());}
int keta(ll x){ if(x<10){return 1;} else{return keta(x/10) + 1;}}

int main(){
  string s; cin >> s;
  int s_size = s.size();
  string k = "keyence";
  int k_size = k.size();
  string temp;
  bool r = false;
  REP(i,k_size+1){
    int j = k_size - i;
    temp = s.substr(0,i) + s.substr(s_size-j,j);
    if(temp==k){r = true; break;}
  }
  cout << (r? "YES\n":"NO\n");
}

Measured memory_bytes: 256
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from math import sqrt
def main():
    n, d = map(int, input().split())
    m = map(int, read().split())
    ab = zip(m, m)
    r = 0
    for a, b in ab:
        dis = sqrt(a**2 + b**2)
        r += dis <= d

    print(r)

if __name__ == '__main__':
    main()


Measured memory_bytes: 42172
n,m = map(int,input().split())
l = [0 for _ in range(m)]

for i in range(n):
    k = list(map(int,input().split()))
    for j in range(1,len(k)):
        l[k[j]-1] += 1
c = 0
for i in l:
    if(i == n):c += 1
print(c)

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

#define ll long long
#define mod 1000000007
#define IO_fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int main(){
    IO_fast
    double d, t, s;
    cin >> d >> t >> s;
    double time = d/s;
    if(time>t) cout << "No" << endl;
    else cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 3732
"use strict"
const create = () => {
    const input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split("\n");
    const res = {
        "list": input, "index": 0, "max": input.length,
        "hasNext": function() {return this.index < this.max},
        "next": function() { if (!this.hasNext()) {throw "ArrayIndexOutOfBoundsException";}else{return this.list[this.index++];}}
    };
    return res;
}
const o = create();
const next = () => o.next()
const nextInt = () => parseInt(o.next())
const nextStrArray = () => o.next().split(" ")
const nextIntArray = () => o.next().split(" ").map(el => parseInt(el))
const nextCharArray = () => o.next().split("")
const hasNext = () => o.hasNext()
const myout = (...x) => console.log(...x)
const Main = () => {
    let n = nextInt()
    let i = Number.POSITIVE_INFINITY
    let j = Number.POSITIVE_INFINITY
    for(let k = 1; k<=Math.ceil(Math.sqrt(n));k++){
        if(n % k == 0){
            let l = n / k
            if(k+l < i+j){
                [i,j] = [k,l]
            }
        }
    }
    console.log(i+j-2)
}
Main()



Measured memory_bytes: 33420
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())
a = list( map(int, input().split()))

ans = 0
cnt = 0
for i in range(1,n):
    if a[i] == a[i-1]:
        cnt +=1
    else:
        ans += -(-cnt//2)
        cnt = 0

ans += -(-cnt//2)
cnt = 0

print(ans)

Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100003;
int n;
struct Node{
	int id;
	ll d;
	bool operator < (const Node &a) const
	{
		return d>a.d;
	}
}a[N];
int siz[N],u[N],v[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		a[i].id=i;
		scanf("%lld",&a[i].d);
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
		siz[i]=1;
	ll dis=0;
	for(int i=1;i<n;i++)
	{
		ll d=a[i].d-n+siz[a[i].id]+siz[a[i].id];
		int x=lower_bound(a+1,a+n+1,(Node){0,d})-a;
		if(a[x].d!=d)
		{
			puts("-1");
			return 0;
		}
		u[i]=a[i].id,v[i]=a[x].id;
		siz[a[x].id]+=siz[a[i].id];
		dis+=siz[a[i].id];
	}
	if(dis!=a[n].d)
	{
		puts("-1");
		return 0;
	}
	for(int i=1;i<n;i++)
		printf("%d %d\n",u[i],v[i]);
	return 0;
}

Measured memory_bytes: 4096
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include<functional>
#include<numeric>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>
#include<bitset>
#include<random>

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define rep(i,n) FOR(i,0LL,n)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define rrep(i,n) RFOR(i,0LL,n)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define COUNT(a,y,x) upper_bound(all(a), y) - lower_bound(all(a), x)
#define UNIQUE(a) sort(all(a)); a.erase(unique(all(a)), a.end())
#define pb push_back
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef map<ll, ll> MAP;
const ll inf = 2222222222222222222LL;
const ll mod = 1000000007LL;
//const ll mod = 998244353LL;

ll n = 0, m = 0, ans = 0, tmp = 0, ma = -inf, mi = inf;
string s;
bool ok;
ll dx[9] = { 0,1,0,-1,0,1,1,-1,-1 }, dy[9] = { 0,0,1,0,-1,1,-1,1,-1 };
#define endl '\n'
#pragma endregion
#define MAX 222222



ll a[22][22];
ll dp[1 << 22];



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



  cin >> n;
  rep(i, n) rep(j, n) cin >> a[i][j];
  dp[0] = 1;
  rep(bit, 1 << n) {
    ll cnt = 0;
    rep(i, n) if (bit >> i & 1) cnt++;
    rep(i, n) {
      if (bit >> i & 1 || !a[i][cnt]) continue;
      (dp[bit | (1 << i)] += dp[bit]) %= mod;
    }
  }

  cout << dp[(1 << n) - 1] << endl;



  return 0;
}

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

/* 大文字を小文字に変換 */
char tolower(char c) {return (c + 0x20);}
/* 小文字を大文字に変換 */
char toupr(char c) {return (c - 0x20);}

// if('A'<=s[i] && s[i]<='Z') s[i] += 'a'-'A';

/*
string s = "abcdefg"
s.substr(4) "efg"
s.substr(0,3) "abc"
s.substr(2,4) "cdef"

// イテレータ要素のインデックス
distance(A.begin(), itr);
*/

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

    int ans = 0;
    for(char c1 ='0'; c1<='9'; c1++){
        for(char c2 ='0'; c2<='9'; c2++){
            for(char c3 ='0'; c3<='9'; c3++){
                bool isc1 = false, isc2 = false, isc3 = false;
                rep(i,n){
                    if(!isc1 && s[i] == c1){
                        isc1 = true;
                        continue;
                    }
                    if(isc1 && !isc2 && s[i] == c2){
                        isc2 = true;
                        continue;
                    }
                    if(isc2 && !isc3 && s[i] == c3){
                        isc3 = true;
                        break;
                    }
                }
                if(isc1 && isc2 && isc3) ans++;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3700
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main(){
  int n, v[110];
  long long dp[110][21];
  
  cin >> n;
  for(int i = 0 ; i < n ; i++){
    cin >> v[i];
  }
  
  memset(dp, 0, sizeof(dp));
  
  dp[0][v[0]] = 1;
  
  for(int i = 0 ; i < n-1 ; i++){
    for(int j = 0 ; j <= 20 ; j++){
      if(j+v[i+1] <= 20) dp[i+1][j+v[i+1]] += dp[i][j];
      if(j-v[i+1] >= 0) dp[i+1][j-v[i+1]] += dp[i][j];
    }
  }
  cout << dp[n-2][v[n-1]] << endl;
  return 0;
}

      

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

H_ls = list(map(int, input().split(" ")))

h_left = H_ls[0]-1

ans = "Yes"
for h in H_ls:
    if h_left < h:
        h-=1
    elif h_left > h:
        ans = 'No'
        break
    h_left = h

print(ans)


Measured memory_bytes: 14252
a,b=map(int,input().split())
c=[0]+[list(map(int,input().split())) for i in range(a)]
print()
def f(t,s):
	if t==0:
		return 10**9
	#点数が高いものを解けるだけとく
	#問題数or目標点数を満たす数
	l=min(s//(t*100),c[t][0])
	k=100*t*l

	#ボーナスを加味
	if l==c[t][0]:
		k+=c[t][1]
	#目標まで足りていないならその下の点数について再帰
	if k<s:
		l+=f(t-1,s-k)
	#その下の点数について再帰（ボーナスを加味するため）	
	return min(l,f(t-1,s))

print(f(a,b))


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

int main(int argc, char const *argv[]) {
  int a, b;
  cin >> a >> b;
  if (a <= 2 * b) {
    cout << "0" << endl;
  } else {
    cout << a - 2 * b << endl;
  }
  return 0;
}


Measured memory_bytes: 256
n=int(input())
factors=[]
i=2
def checker(power):
    l=1
    r=20
    ans=1
    while l<=r:
        mid=l+(r-l)//2
        if mid*(mid+1)/2<=power:
            ans=mid
            l=mid+1
        else:
            r=mid-1
    return ans
while i**2<=n:
    if n%i==0:
        cnt=0
        while n%i==0:
            n/=i
            cnt+=1
        factors.append([i,cnt])
    i+=1
if n>1:
    factors.append([n,1])

res=0
rem=0
for i in range(len(factors)):
    a=checker(factors[i][1])
    res+=a
    factors[i][1]-=a
    rem+=factors[i][1]
'''if rem>1:
    res+=rem*(rem-1)/2'''
#print(factors)
print(int(res))

Measured memory_bytes: 9128
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long num = sc.nextLong();
		int ans = 0;
		if (num > 1) {
			Map<Long, Long> factorMap = new HashMap<Long, Long>();
			Main main = new Main();
			main.factoring(factorMap, num);
			int con = 0;

			for (Long item : factorMap.keySet()) {
				con = 1;
				long val = factorMap.get(item);
				while (con <= val) {
					val = val - con;
					con++;
					ans++;
				}
			}
		}

		System.out.println(ans);

	}

	public void factoring(Map<Long, Long> factorMap,long num) {
		boolean isFactoringFlg = false;
		for (int i = 2; i <= Math.sqrt(num); i++) {
			if (num % i == 0 ) {
				if (factorMap.containsKey((long)i)) {
					factorMap.put((long)i, factorMap.get((long)i) + 1L);
				} else {
					factorMap.put((long)i, 1L);
				}
				num = num / i;
				isFactoringFlg = true;
				break;
			}
		}

		if (isFactoringFlg) {
			factoring(factorMap, num);
		}else {
			if (factorMap.containsKey(num)) {
				factorMap.put(num, factorMap.get(num) + 1L);
			}else {
				factorMap.put(num, 1L);
			}
		}
	}
}

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

public class Main {

	static int N;
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		for(;;){
			N=sc.nextInt();
			if(N==0)break;
			C[] c = new C[N];
			for(int i=0;i<N;i++){
				String name=sc.next();
				c[i]=new C(name);
				int m = sc.nextInt();
				for(int j=0;j<m;j++){
					c[i].time[sc.nextInt()]=1;
				}
			}
			for(int i=0;i<31;i++){
				int p = N+1;
				for(int j=0;j<N;j++){
					if(c[j].time[i]==1){
						p--;
					}
				}
				for(int j=0;j<N;j++){
					if(c[j].time[i]==1){
						c[j].point+=p;
					}
				}
			}
			Arrays.sort(c);
			int p = c[0].point;
			for(int i=0;i<N;i++){
				if(c[i].point==p){
//					System.out.println(c[i]);
				}
			}
			System.out.println(c[0]);
		}
	}
	static class C implements Comparable<C>{
		String name;
		int[] time;
		int point;
		
		C(String s){
			name=s;
			time=new int[31];
		}
		public int compareTo(C c){
			if(point==c.point){
				return name.compareTo(c.name);
			}
			return point-c.point;
		}
		public String toString(){
			return point +" " + name;
		}
	}
}

Measured memory_bytes: 31956
#include <bits/stdc++.h>
 
using namespace std;
 
#define EPS 1e-10
#define INF 1e8
#define equal(a,b) (fabs(a-b) < EPS)
#define not_equal(a,b) (!equal(a,b))
#define lt(a,b) (a-b < -EPS)
 
struct Point{
    double x,y;
 
    Point(){}
    Point(double x,double y) : x(x),y(y) {}
 
    Point operator + (const Point &p)const{ return Point(x+p.x,y+p.y); }
    Point operator - (const Point &p)const{ return Point(x-p.x,y-p.y); }
    Point operator * (const double &k)const{ return Point(x*k,y*k); }
    Point operator / (const double &k)const{ return Point(x/k,y/k); }
    bool operator < (const Point &p)const{ return x != p.x ? x < p.x : y < p.y; }
};
 
istream &operator >> (istream &is,Point &p){ 
    return is >> p.x >> p.y;
}
 
double dot(const Point &a,const Point &b){ return a.x*b.x+a.y*b.y; }
double cross(const Point &a,const Point &b){ return a.x*b.y - b.x*a.y; }
double norm(const Point &p){ return dot(p,p); }
double dist(const Point &a,const Point &b){
    return sqrt(pow(a.x-b.x,2) + pow(a.y-b.y,2));
}
 
#define COUNTER_CLOCKWISE 1
#define CLOCKWISE -1
#define ONLINE_BACK 2
#define ONLINE_FRONT -2
#define ON_SEGMENT 0
typedef Point Vector;
 
int ccw(Point p0,Point p1,Point p2){
    Vector a = p1 - p0;
    Vector b = p2 - p0;
    if(cross(a,b) > EPS) return COUNTER_CLOCKWISE;
    if(cross(a,b) < -EPS) return CLOCKWISE;
    if(dot(a,b) < -EPS) return ONLINE_BACK;
    if(norm(a) < norm(b)) return ONLINE_FRONT;
    return ON_SEGMENT;
}
 
struct Segment{
    Point s,t;
    Segment(){}
    Segment(Point s,Point t) : s(s),t(t) {}
};
 
bool isIntersectSP(const Segment &s,const Point &p){
    return equal(ccw(s.s,s.t,p),0);
}
 
bool isIntersectSS(const Segment &a,const Segment &b){
    Point s[2] = {a.s,a.t}, t[2] = {b.s,b.t};
    return (ccw(s[0],s[1],t[0])*ccw(s[0],s[1],t[1]) <= 0 &&
	    ccw(t[0],t[1],s[0])*ccw(t[0],t[1],s[1]) <= 0);
}
 
struct State{
    double d;
    int v;
    State(double d,int v) : d(d),v(v) {}
   
    bool operator < (const State &s)const{
	if(not_equal(d,s.d)){
	    return lt(s.d,d);
	}
    }
};
 
double solve(int x,vector<Point> A[2]){
    priority_queue<State> Q;
    Q.push(State(0,0));
    double d[1010];
    fill(d,d+1010,INF);
    d[0] = 0;
   
    while(!Q.empty()){
	State s = Q.top(); Q.pop();
	int v = s.v;
	if(lt(d[v],s.d)) continue; 
	if(v == 1) return d[v];
	for(int i = 1 ; i < (int)A[x].size() ; i++){
	    if(v == i) continue;
	    Segment s1(A[x][v],A[x][i]),s2(A[1-x][0],A[1-x][1]);
	    if(isIntersectSS(s1,s2)) continue;
	    double nd = d[v]+dist(A[x][v],A[x][i]);
	    if(lt(nd,d[i])){
		d[i] = nd;
		Q.push(State(d[i],i));
	    }
	}
    }
    return INF;
}
 
int main(){
    int N,M;
    vector<Point> A[2];
    cin >> N >> M;
    A[0].resize(N); A[1].resize(M);
    for(int i = 0 ; i < N ; i++){
	cin >> A[0][i];
    }
    for(int i = 0 ; i < M ; i++){
	cin >> A[1][i];
    }
    double res = INF;
    Segment s[2] = {Segment(A[0][0],A[0][1]),
		    Segment(A[1][0],A[1][1])};
    for(int i = 0 ; i < 2 ; i++){
	res = min(res,solve(1-i,A)+dist(s[i].s,s[i].t));
    }
    if(res == INF){
	cout << -1 << endl;
    }else{
	printf("%.10f\n",res);
    }
    return 0;
}

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

using namespace std;

using lli = long long int;
using ulli = unsigned long long int;

#define EVEL 1

#ifndef EVEL
#define dbug(X) std::cout << #X << ":" <<X<<" " ;
#define dbugf(s) std::cout << s << " ";
#define dbugln std::cout<<"\n";
#else
#define dbug(X) {}
#define dbugf(s) {}
#define dbugln {}
#endif

int n;
ulli a, s;
ulli b[200010];

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

	cin >> n;
	if(n % 2 == 0){
		for(int i = 1; i <= n; i++){
			cin >> a;
			if(i%2 == 0){
				b[n/2-(i/2)] = a;
			}else{
				b[n/2+(i/2)]=a;
			}
		}
	}else{
		for(int i = 1; i <= n; i++){
			cin >> a;
			if(i%2 == 0){
				b[n/2+(i/2)] = a;
			}else{
				b[n/2-(i/2)] = a;
			}
		}
	}

	for(int i = 0; i < n-1; i++){
		cout << b[i] << " ";
	}
	cout << b[n-1] << endl;
  return 0;
}


Measured memory_bytes: 3712
n,m = map(int,input().split())

a = []
for i in range(n):
  a.append(list(map(int,input().split())))

b = []
for i in range(m):
  b.append(int(input()))

c = []

for i in range(n):
  r = 0
  for j in range(m):
    r += a[i][j]*b[j]
  c.append(r)

print(*c,sep='\n')


Measured memory_bytes: 6016
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vl vaector<long>
#define vll vector<long long int>
#define vC  vector<char>
#define FastIO ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define db(...) ZZ(#__VA_ARGS__, __VA_ARGS__)
ll pow(ll x, ll y,ll m) { ll res = 1;x=x%m; while (y > 0) { if (y & 1) res = ((res%m) * (x%m))%m; y = y >> 1; x = ((x%m) * (x%m))%m; } return res%m; }
template <typename Arg1> void ZZ(const char* name, Arg1&& arg1){std::cerr << name << " = " << arg1 << endl;}
template <typename Arg1, typename... Args>void ZZ(const char* names, Arg1&& arg1, Args&&... args)
{
	const char* comma = strchr(names + 1, ',');
	std::cerr.write(names, comma - names) << " = " << arg1;
	ZZ(comma, args...);
}
const ll INF = 0xFFFFFFFFFFFFFFFL;
clock_t time_p=clock();
void abhigyan10()
{time_p=clock()-time_p;cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";}
ll seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline ll rnd(ll l=0,ll r=INF){return uniform_int_distribution<ll>(l,r)(rng);}
#define clrbuf cin.ignore(numeric_limits<streamsize>::max(),'\n');
#define preciset(x) cout<<setprecision(x)<<fixed;
const ll mod =1000000007;

int main()
{
        FastIO
        int i;
		string s;
        cin>>s;
        reverse(s.begin(),s.end());
        vector<ll> dp(s.length()+1),dp2(s.length()+1);

        dp[1]=(s[0]-'0');
        dp2[1]=10-(s[0]-'0');
        for(i=1;i<s.length();i++)
        {
        	dp[i+1]= min(dp2[i]+ (s[i]-'0' )+1,dp[i]+(s[i]-'0' ));
        	dp2[i+1]=min(dp2[i]+ 10-(s[i]-'0'+1),dp[i]+10-(s[i]-'0'));

        	
        }


        cout<<min(dp[s.length()],dp2[s.length()]+1);
        return 0;
    }


Measured memory_bytes: 17052
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef long long ll;
#define test ll t;cin>>t;while(t--)
#define f first
#define s second
#define pb push_back
#define pop pop_back
#define int long long int
#define mod 1000000007
#define inf 1LL<<60


int dp[22][1<<22];

int solve(vector<vector<int> > &compat,int i,int womansubset,int N)
{
    if(i== N+1)
    {
        if(womansubset==0)
            return 1;
        return 0;
    }

    if(dp[i][womansubset]!=-1)
        return dp[i][womansubset];

    int ans =0;
    for(int woman = 0;woman<N;woman++)
    {
        bool available = (((1<<woman)&(womansubset))==0)?0 : 1;

        if(available && compat[i][woman+1])
        {
        ans = (ans + solve(compat,i+1,womansubset^(1<<woman),N))%mod;
        }
    }

    return dp[i][womansubset] = ans;
}

int32_t main()
{
	fast;
	int n;
    cin>>n;
    vector< vector<int > >compat(n+1, vector<int>(n+1));

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
          cin>>compat[i][j];

    memset(dp,-1,sizeof dp);

    cout<<solve(compat,1, ((1<<(n))-1) ,n)<<"\n";

	return 0;
}



Measured memory_bytes: 721152
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define bit(n) (1<<(n))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
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 const INF = 1001001001;


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

string s;
cin >> s;
int n = SZ(s);

int ans = 0;
int r =(n+1)/2;

rep(i,n) {
    if(i < r) {
        if(s[i] == 'p') ans--;
    }
    else {
        if(s[i] == 'g') ans++;
    }
}
cout << ans << endl;
return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
string a;
int x=0,y=0,ans=0;
int main(){
    cin>>a;
    int len=a.size();
    for(int i=0;i<len;i++){
        if(x==y){
            x++;
            if(a[i]=='p') ans--;
        }
        else{
            y++;
            if(a[i]=='g') ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) cin>>aa;(p).push_back(aa);
#define vecpl2(p) long long a	b;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define set0(k,n) for(int nn=0;nn<(n);nn++){ (k).push_back(0); }
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define vecsize(b,size) vector<int> (b)((size));
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsl(s) vector<pair<ll,ll>> (s);
#define pairss(s) vector<pair<string,string>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairspl(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsps(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsREV(s) (s).push_back(make_pair(bb,aa));
#define pairslREV(s) (s).push_back(make_pair(bb,aa));
#define pairssREV(s) (s).push_back(make_pair(bb,aa));
#define MOD 1000000007

int main()
{
	ll S;
	cin >> S;
	ll x1 = 0, y1 = 0, x2 = 1000000000, y2 = 1,x3=-1,y3=-1;
	ll left = 0, right = 1000000001;
	fx(50) {
		y3 = (left + right) / 2;
		ll T = abs(x2 * y3 - S);
		if (T<=1000000000) {
			if (abs(x2*y3-T*y2)==S) {
				x3 = T;
				break;
			}
		}

		if (x2 * y3 - S<0) {
			left = y3;
		}
		else {
			right = y3;
		}
	}
	
	cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << ' ' << x3 << ' ' << y3 << ' ' << endl;

    return 0;
}



Measured memory_bytes: 256
from queue import Queue

n = int(input())
A = [[0 for i in range(n)] for j in range(n)]
d = [-1] * n

for i in range(n):
    u, k, *v = list(map(int, input().split()))
    for j in v:
        A[int(u)-1][int(j)-1] = 1

q = Queue()
q.put(0)
d[0] = 0

while not q.empty():

    u = q.get()

    for v in range(n):

        if A[u][v] == 1 and d[v] == -1:
            q.put(v)
            d[v] = d[u] + 1

for i in range(n):
    print(i+1, d[i])


Measured memory_bytes: 6928
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    if N%10==9 or N//10==9:
        print("Yes")
    else:
        print("No")

main()


Measured memory_bytes: 38256
#![allow(unused_imports, unused_macros, dead_code)]

macro_rules! min {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        it.next().map(|z| it.fold(z, |x, y| min!(x, y)))
    }};
    ($x:expr) => ($x);
    ($x:expr, $($ys:expr),*) => {{
        let t = min!($($ys),*);
        if $x < t { $x } else { t }
    }}
}
macro_rules! max {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        it.next().map(|z| it.fold(z, |x, y| max!(x, y)))
    }};
    ($x:expr) => ($x);
    ($x:expr, $($ys:expr),*) => {{
        let t = max!($($ys),*);
        if $x > t { $x } else { t }
    }}
}
macro_rules! ewriteln {
    ($($args:expr),*) => { let _ = writeln!(&mut std::io::stderr(), $($args),*); };
}
macro_rules! trace {
    ($x:expr) => { ewriteln!(">>> {} = {:?}", stringify!($x), $x) };
    ($($xs:expr),*) => { trace!(($($xs),*)) }
}
macro_rules! put {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        if let Some(x) = it.next() { print!("{}", x); }
        for x in it { print!(" {}", x); }
        println!("");
    }};
    ($x:expr) => { println!("{}", $x) };
    ($x:expr, $($xs:expr),*) => { print!("{} ", $x); put!($($xs),*) }
}

const M: i64 = 1_000_000_007;

fn main() {
    let mut sc = Scanner::new();
    let n: usize = sc.cin();
    let xs: Vec<usize> = sc.vec(n);

    let mut memo = vec![0i64; 200002];
    for &x in xs.iter() { memo[x] += 1; }

    let mut sum = 0;
    for x in 0..200002 { if memo[x] >= 2 { sum += memo[x] * (memo[x] - 1) / 2; } }

    for &x in xs.iter() {
        let mut ans = sum;
        ans -= memo[x] * (memo[x] - 1) / 2;
        if memo[x] >= 3 { ans += (memo[x] - 1) * (memo[x] - 2) / 2; }
        put!(ans);
    }
}

use std::io::{self, Write};
use std::str::FromStr;
use std::collections::VecDeque;

struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, }
impl Scanner {
    fn new() -> Self { Scanner { stdin: io::stdin(), buffer: VecDeque::new() } }
    fn cin<T: FromStr>(&mut self) -> T {
        while self.buffer.len() == 0 {
            let mut line = String::new();
            let _ = self.stdin.read_line(&mut line);
            for w in line.split_whitespace() {
                self.buffer.push_back(String::from(w));
            }
        }
        self.buffer.pop_front().unwrap().parse::<T>().ok().unwrap()
    }
    fn chars(&mut self) -> Vec<char> { self.cin::<String>().chars().collect() }
    fn vec<T: FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.cin()).collect() }
}


Measured memory_bytes: 17540
S, T = input(), input()
ma, ima = {}, {}
ok = True
for i in range(len(S)):
    s, t = S[i], T[i]
    if s in ma and ma[s] != t:
        ok = False
    if t in ima and ima[t] != s:
        ok = False
    ma[s] = t
    ima[t] = s
if ok:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3632
// https://atcoder.jp/contests/abc175/tasks/abc175_d
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <set>
#include <unordered_set>
#include <bitset>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define REP(i, n) for(size_t i = 0; i < (n); ++i)

int main()
{
    ll N, K;
    cin >> N >> K;
    vector<int> P(N), C(N);
    REP(i, N) cin >> P[i], --P[i];
    REP(i, N) cin >> C[i];
    ll ans = -1e+18;
    // スタート地点となる頂点に関するループ
    REP(si, N)
    {
        ll x = si;
        vector<int> scorearray;
        ll tot = 0;
        while (1)
        {
            // 移動先の頂点
            x = P[x];
            scorearray.push_back(C[x]);
            tot += C[x];
            // 順列であることから、一巡する = スタート地点に戻った時
            if (x == si) break;
        }
        ll len = scorearray.size();
        ll sumi = 0; // ループ途中の和
        // どこで切るかを全部試す
        REP(i, len)
        {
            sumi += scorearray[i];
            if (i + 1 > K) break;
            ll nowsum = sumi;
            if (tot > 0)
            {
                ll cycle = (K - i - 1) / len; //(切った残りから周回を算出)
                nowsum += tot * cycle;
            }
            ans = max(ans, nowsum);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3700