akhauriyash/Code-Regression huggingface dataset:
n=int(input())
l=list(map(int,input().split()))
minuscount=0
zerocount=0
for i in range(len(l)):
  if l[i]<0:
    minuscount+=1
  elif l[i]==0:
    zerocount+=1
absl=[abs(l[i]) for i in range(len(l))]
if minuscount%2==0:
  print(sum(absl))
else:
  if zerocount>0:
    print(sum(absl))
  else:
    absl.sort(reverse=True)
    print(int(sum(absl)-2*absl[-1]))

Measured memory_bytes: 14332
#include<bits/stdc++.h>
#define LLI long long int
#define ULTRA 2134567890

using namespace std;

char s[100007];
int arr[100007]={};
int cnt;

int main()
{
    int i,j;

    scanf("%s",s);
    for( i=0; s[i]; )
    {
        cnt= 0;
        j= 0;
        while(s[i]=='R')
        {
            cnt++;
            i++;
            j=!j;
        }
        int idx=i;
        if(j==0)
        {
            arr[idx]+= cnt/2;
            arr[idx-1]+= cnt/2;
        }
        else
        {
            arr[idx]+= cnt/2;
            arr[idx-1]+= cnt/2+1;
        }

        j=0;
        cnt=0;
        while(s[i] && s[i]=='L')
        {
            cnt++;
            i++;
            j=!j;
        }

        if(j==0)
        {
            arr[idx-1]+= cnt/2;
            arr[idx]+= cnt/2;
        }
        else
        {
            arr[idx-1]+= cnt/2;
            arr[idx]+= cnt/2+1;
        }

    }
    for( i=0; s[i]; i++)
    {
        printf("%d ",arr[i]);
    }
    printf("\n");

    return 0;
}


Measured memory_bytes: 896
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>

#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
#define REMOVE(v,a) v.erase(remove(v.begin(), v.end(), a), v.end())
#define REP(i,n) for (int (i) = 0; (i) < (n); (i)++)
using namespace std;

int N, A, B;
int h[100000];

bool can_destroy(int cnt)
{
	int c = cnt;
	REP(i, N)
	{
		int a = h[i] - cnt * B;
		int S = A - B;
		if (a > 0)
		{
			int n = a / S;
			if (a - n * S > 0)
			{
				n++;
			}
			c -= n;
			if (c < 0)
			{
				return false;
			}
		}
	}
	return true;
}

signed main()
{
	cin >> N >> A >> B;
	REP(i, N) cin >> h[i];

	int l = 0;
	int r = 1000000000;

	while (true)
	{
		if (r - l <= 1) break;
		int m = (r - l) / 2 + l;
		if (can_destroy(m))
		{
			r = m;
		}
		else
		{
			l = m;
		}
	}

	cout << r << endl;
}

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

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);  
	int p[3][3];
	int a, b, c, d;
	for(int i = 0; i < 3; i++) {
		for(int j = 0; j < 3; j++) {
			cin >> p[i][j];
		}
	}
	a = p[0][1] - p[0][0];
	b = p[0][2] - p[0][1];
	c = p[1][0] - p[0][0];
	d = p[2][0] - p[1][0];
	for(int i = 0; i < 3; i++) {
		if(a != p[i][1] - p[i][0] || b != p[i][2] - p[i][1] || c != p[1][i] - p[0][i] || d != p[2][i] - p[1][i]) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;	
}


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

using namespace std;

int main(){
    int N;
    cin >> N;
    vector<int> a(N);
    map<int, int> Count;
    set<int> b;
    
    for(int i = 0; i < N; ++i){
        cin >> a[i];
        Count[a[i]]++;
        b.insert(a[i]);
    }
    
    int ans = 0;
    
    for(auto el:b){
        int num = el;
        int tmp = Count[num - 1] + Count[num] + Count[num + 1];
        ans = max(ans, tmp);
    }
    cout << ans << endl;
    
}

Measured memory_bytes: 8064
import collections
AC=0
WA=0
TLE=0
RE=0
N=int(input())
S=[]
for i in range(N):
  S.append(input())
count=collections.Counter(S)
print("AC x {}".format(count["AC"]))
print("WA x {}".format(count["WA"]))
print("TLE x {}".format(count["TLE"]))
print("RE x {}".format(count["RE"]))

Measured memory_bytes: 16576
using System;

namespace AOJ
{
    class Program
    {
        static void Main()
        {
            string[] str = (Console.ReadLine()).Split(' ');
            int a = int.Parse(str[0]);
            int b = int.Parse(str[1]);

            if (a < b)
                Console.WriteLine("a < b");
            else if(a > b)
                Console.WriteLine("a > b");
            else if(a == b)
                Console.WriteLine("a == b");
        }
    }
}

Measured memory_bytes: 8784
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
const int INF = 2000000000;
using namespace std;

const int gmax_n = 100005;

int par[gmax_n]; //???
int depth[gmax_n];//??¨?????±???

void init(int n){
    rep(i,n){
        par[i] = i;
        depth[i] = 0;
    }
}

int find(int x){
    if(par[x] == x){
        return x;
    }else {
        return par[x] = find(par[x]);
    }
}

void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y) return;

    if(depth[x] > depth[y]){
        par[x] = y;
    }else{
        par[y] = x;
    }
}

bool same(int x, int y){
    return find(x) == find(y);
}

void dfs(vector<int> t[gmax_n], int g[gmax_n], int cur){
    rep(i,t[cur].size()){
        int next = t[cur][i];
        if(g[next] != -1) continue;

        depth[next] = depth[cur] + 1;
        g[next] = cur;
        dfs(t,g,next);
    }
}

int main(){
    int n, m;
    while(cin >> n >> m, n||m){
        vector<int> tree[gmax_n];
        init(n);
        rep(i,n - 1){ //??¨????§????
            int a;
            cin >> a;
            a--;
            tree[i + 1].emplace_back(a);
            tree[a].emplace_back(i + 1);
        }

        bool marked[gmax_n] = {false};//???????????????????????????????¨????
        marked[0] = true;
        vector<pair<char, int>> q;
        rep(i,m){
            char a;
            int b;
            cin >> a >> b;
            b--;
            if(a == 'M'){
                if(marked[b]) continue; //????????¨???????????????????????´?????????????????\???????????????
                else{
                    marked[b] = true;
                    q.emplace_back(make_pair(a, b));
                }
            }else{
                q.emplace_back(make_pair(a,b));
            }
        }

        int g[gmax_n] = {0};
        range(i,1,gmax_n) g[i] = -1;
        dfs(tree, g, 0);

        rep(i,n){
            if(not marked[i]) unite(g[i], i);
        }

        //rep(i,n) show(g[i])
        //rep(i,n){ show(find(i)) }
        //rep(i,n){ show(depth[i]) }

        long long ans = 0;
        for(int i = q.size() - 1; i >= 0; i--){ //?????¨?????????????????????
            if(q[i].first == 'Q') ans += find(q[i].second) + 1;
            else{
                unite(g[q[i].second], q[i].second);
            }
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 18104
#include<stdio.h>

int simulation(int num[], char vec[], int i){
    int v;
    if(vec[i] == 'N'){
        v = num[0];
        num[0] = num[1];
        num[1] = num[5];
        num[5] = num[4];
        num[4] = v;
    }else if(vec[i] == 'S'){
        v = num[0];
        num[0] = num[4];
        num[4] = num[5];
        num[5] = num[1];
        num[1] = v;
    }else if(vec[i] == 'E'){
        v = num[0];
        num[0] = num[3];
        num[3] = num[5];
        num[5] = num[2];
        num[2] = v;
    }else if(vec[i] == 'W'){
        v = num[0];
        num[0] = num[2];
        num[2] = num[5];
        num[5] = num[3];
        num[3] = v;
    }
    return num[0];
}

int main(){
    int i, n;
    int num[6];
    char vec[100];

    for(i = 0; i < 6; i++){
        scanf("%d", &num[i]);
    }
    scanf("%s", vec);

    for(i = 0; vec[i] != '\0'; i++){
        n = simulation(num, vec, i);
    }
    printf("%d\n", n);

    return 0;
}


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

#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pf printf
#define sc scanf
#define sf(num) scanf("%d",&num)
#define sff(num1,num2) scanf("%d %d",&num1,&num2)
#define sfff(num1,num2,num3) scanf("%d %d %d",&num1,&num2,&num3)
#define sl(num) scanf("%lld",&num)
#define sll(num1,num2) scanf("%lld %lld",&num1,&num2)
#define slll(num1,num2,num3) scanf("%lld %lld %lld",&num1,&num2,&num3)
#define rep(i,n) for(i=1;i<=n;i++)
#define rep0(i,n) for(i=0;i<n;i++)
#define reps(i,a,n) for(i=a;i<=n;i++)
#define pb push_back
#define mpp make_pair
#define MOD 1000000007
#define fi first
#define se second
#define N 100005
#define mem(ara,n) memset(ara,n,sizeof(ara))
#define memb(ara) memset(ara,false,sizeof(ara))
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define pi pair<int,int>
#define pii pair<pair<int,int>,pair<int,int> >
#define db(x) cout<<#x<<" :: "<<x<<"\n";
#define dbb(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\n";
#define fr freopen("input.txt","r",stdin);
#define fw freopen("output.txt","w",stdout);
#define TIME cerr<<"Time : "<<(double)clock()/(double)CLOCKS_PER_SEC<<"s\n";
typedef long long int ll;
using namespace std;
int ara[N];
int main()
{
    int n,k,q;
    sfff(n,k,q);
    int i,p;
    rep0(i,q)
    {
        sf(p);
        ara[p]++;
    }
    rep(i,n)
    {
        if(ara[i]+k-q>0)
            puts("Yes");
        else
            puts("No");
    }
}


Measured memory_bytes: 1024
N, K = map(int, input().split())
pi = list(map(int, input().split()))

tmp = sum(pi[0 : K])
max = tmp

if N == K:
    print((max + K) / 2)
else:
    for i in range(N - K):
        tmp = tmp - pi[i] + pi[i + K]
        if tmp > max:
            max = tmp
    print((max + K) / 2)

Measured memory_bytes: 25060
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

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

    int n = s.size()-1;
    ll sol = 0;
    for(int bit = 0; bit < (1<<n); bit++){
        ll now = 0;
        //cout << bitset<8>(bit) << endl;
        for(int i = 0; i < n+1; i++){
            now *= 10;
            now += s[i] - '0';
            if(!(bit&(1<<i))){  //bitが立ってない -> +があるので加算   bitが立ってる -> +がない
                //cout << bitset<8>(bit&(1<<i)) << endl;
                //cout << now << endl;
                sol += now;
                now = 0;
            }
        }
    }

    cout << sol << endl;

    return 0;
}

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

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,x,n) for(int i=x; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()
#define X first
#define Y second
#define pb push_back
#define eb emplace_back

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

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

template<class A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); }

const ll INF = 0x3fffffff;


int main(){
	//ios_base::sync_with_stdio(0);
	int N, ans=0;
	ll K;

	cin >> K;

	vector<ll> v(50,49);
	rep(i,50) v[i] += K/50;
	//rep(i,50) cout << v[i] << " "; cout << endl;
	rep(i,K%50){
		v[i] += 50;
		rep(j,50) if(i!=j) v[j]--;
	}

	cout << 50 << endl;
	rep(i,50) cout << v[i] << " "; cout << endl;

//	cout << 2 << endl;
//	if( K%2 ){
//		cout << 1+(K/2) << " " << 1+K/2 << endl;
//	}else{
//		cout << (K/2) << " " << 2+(K+1)/2 << endl;
//	}

	return 0;
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int bitArray[] = new int[64];
		int n = sc.nextInt();
		//int mask[][] = new int[n][64];
		List<List<Integer>> mask = new ArrayList<List<Integer>>(n);

		for(int i = 0; i < n; i++) {
			mask.add(new ArrayList<Integer>());
		}

		for(int i = 0; i < n; i++) {
			int k = sc.nextInt();
			for(int j = 0; j < k; j++) {
				int b = sc.nextInt();
				mask.get(i).add(b);
			}
		}

		int q = sc.nextInt();
		for(int i = 0; i < q; i++) {
			boolean flag = false;
			int query = sc.nextInt();
			int m = sc.nextInt();

			switch(query) {
			case 0:
				System.out.println(bitArray[m]);
				break;
			case 1:
				for(int j = 0; j < mask.get(m).size(); j++) {
					bitArray[mask.get(m).get(j)] = 1;
				}
				break;
			case 2:
				for(int j = 0; j < mask.get(m).size(); j++) {
					bitArray[mask.get(m).get(j)] = 0;
				}
				break;
			case 3:
				for(int j = 0; j < mask.get(m).size(); j++) {
					bitArray[mask.get(m).get(j)] = (bitArray[mask.get(m).get(j)] + 1) % 2;
				}
				break;
			case 4:  //all->全てのフラグがONになっている場合1、なっていない場合0を出力
				for(int j = 0; j < mask.get(m).size(); j++) {
					if(bitArray[mask.get(m).get(j)] == 0) {
						flag = true;  //1つでもオフのフラグがあればtrueにする
						break;
					}
				}
				if(flag) System.out.println(0);
				else System.out.println(1);
				break;
			case 5:  //any->何れかのフラグがONになっている場合1、なっていない場合0を出力
				for(int j = 0; j < mask.get(m).size(); j++) {
					if(bitArray[mask.get(m).get(j)] == 1) {
						flag = true;
						break;
					}
				}
				if(flag) System.out.println(1);
				else System.out.println(0);
				break;
			case 6:  //none->全てのフラグがOFFになっている場合1、なっていない場合0を出力
				for(int j = 0; j < mask.get(m).size(); j++) {
					if(bitArray[mask.get(m).get(j)] == 1) {
						flag = true;  //1つでもオフのフラグがあればtrueにする
						break;
					}
				}
				if(flag) System.out.println(0);
				else System.out.println(1);
				break;
			case 7:  //count->
				int count = 0;
				for(int j = 0; j < mask.get(m).size(); j++) {
					if(bitArray[mask.get(m).get(j)] == 1) count++;
				}
				System.out.println(count);
				break;
			case 8:  //val->
				long state = Long.MIN_VALUE;
				for(int j = 0; j < mask.get(m).size(); j++) {
					if(bitArray[mask.get(m).get(j)] == 1) {
						state += (long)Math.pow(2, mask.get(m).get(j));
					}
				}
				if(state < -1) {
					System.out.println(state + Long.MAX_VALUE + 1);
					break;
				}
				else {
					System.out.println(Long.toUnsignedString(state + Long.MAX_VALUE + 2));
					break;
				}
			}
		}
	}

}



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

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

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

const int MAX = 1e5 + 5;
const int INF = 1001001001;
const int MOD = 1e9 + 7;

int digit(int i) {
    if (i == 0) return 1;
    int res = 0;
    while (i > 0) {
        res++;
        i /= 10;
    }
    return res;
}

bool check(int i, vector<set<int>> &V) {
    string s = to_string(i);

    rep(i, V.size()) {
        if (V[i].empty()) continue;
        int n = *V[i].begin();
        if ((s[i] - '0') != n) return false;
    }

    return true;
}

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

    vector<int> S(M), C(M);
    rep(i, M) cin >> S[i] >> C[i];

    vector<set<int>> V(N);
    rep(i, M) {
        int s = S[i];
        s--;
        V[s].insert(C[i]);
    }

    for (auto &i : V) {
        if (1 < i.size()) {
            puts("-1");
            return 0;
        }
    }

    rep(i, 1000) {
        if (digit(i) == N && check(i, V)) {
            cout << i << endl;
            return 0;
        }
    }

    puts("-1");
}

Measured memory_bytes: 256
#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部定数
#define D_CHAR_MAX		1000005									// 最大文字数

// 内部変数
static FILE *szpFpI;											// 入力
static char sc1Str[D_CHAR_MAX];									// 文字列
static int siCCnt;												// 文字数

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpA;
	static int siTNo;
#endif

// １行出力
int
fOutLine(
	char *pcpLine				// <I> １行
)
{
	char lc1Buf[1024];

#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, pcpLine)) {
		siRes = -1;
	}
#else
	printf("%s", pcpLine);
#endif

	return 0;
}

// 実行メイン
int
fMain(
)
{
	int i, j;
	char lc1Buf[1024];

	// 文字数 - 取得
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d", &siCCnt);

	// 文字列 - 取得
	fgets(sc1Str, sizeof(sc1Str), szpFpI);

	// クエリ数 - 取得
	int liQCnt;
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d", &liQCnt);

	// クエリ - 取得
	for (i = 0; i < liQCnt; i++) {
		int liLen;
		fscanf(szpFpI, "%d", &liLen);

		// DMC数 - 取得
		long long llDCnt = 0;
		long long llMCnt = 0;
		long long llDMCnt = 0;
		long long llDMCCnt = 0;
		for (j = 0; j < siCCnt; j++) {

			// 文字削除
			if (j >= liLen) {
				if (sc1Str[j - liLen] == 'D') {
					llDCnt--;
					llDMCnt -= llMCnt;
				}
				else if (sc1Str[j - liLen] == 'M') {
					llMCnt--;
				}
			}

			// 文字追加
			if (sc1Str[j] == 'D') {
				llDCnt++;
			}
			else if (sc1Str[j] == 'M') {
				llMCnt++;
				llDMCnt += llDCnt;
			}
			else if (sc1Str[j] == 'C') {
				llDMCCnt += llDMCnt;
			}
		}

		// 出力
		sprintf(lc1Buf, "%lld\n", llDMCCnt);
		fOutLine(lc1Buf);
	}
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);

	return 0;
}

// １回実行
int
fOne(
)
{
	int liRet;
	char lc1Buf[1024];

	// 入力 - セット
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);
	szpFpI = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#else
	szpFpI = stdin;
#endif

	// 実行メイン
	liRet = fMain();

	// 残データ有無
#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, "")) {
		siRes = -1;
	}
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpI);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", siTNo);
	}
	else {
		printf("NG %d\n", siTNo);
	}
#endif

	return 0;
}

// プログラム開始
int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		siTNo = i;
		fOne();
	}
#else
	fOne();
#endif

	return 0;
}



Measured memory_bytes: 1152
from collections import Counter
n = int(input())
assert n >= 2
a = [int(x) for x in input().split()]
assert len(a) == n
ap = Counter([i + x for i, x in enumerate(a)])
am = Counter([i - x for i, x in enumerate(a)])
count = sum([v * ap.get(k, 0) for k, v in am.items() if k >= 1])
print(count)


Measured memory_bytes: 61692
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
  int N, T, K;
  cin >> N >> T;
  K=0;
  vector<int> c(N);
  vector<int> t(N);
  for (int i=0; i<N; i++) {
    cin >> c.at(i) >> t.at(i);
  }
  for (int j=0; j<N; j++) {
    if (t.at(j)>T) {
      c.at(j)=5000;
      K=K+1;
    }
  }
  sort(c.begin(),c.end());
  if (K==N) {
    cout << "TLE" << endl;
  }
  else {
    cout << c.at(0) << endl;
  }
}

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define sf scanf
#define pf printf
#define pb push_back
#define mp make_pair
#define PI ( acos(-1.0) )
#define mod 998244353LL
#define IN freopen("C.in","r",stdin)
#define OUT freopen("output.txt","w",stdout)
#define FOR(i,a,b) for(i=a ; i<=b ; i++)
#define DBG pf("Hi\n")
#define INF 1000000000
#define i64 long long int
#define eps (1e-8)
#define xx first
#define yy second
#define ln 17
#define off 2

using namespace __gnu_pbds;
using namespace std ;

typedef tree< i64, null_type, less<i64>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef pair<i64, i64> pii;

#define maxn 300005

int dp[maxn] ;
deque < pair<int,int> > dq ;
char s[maxn] ;

int main()
{
    int n , m ;

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

    for(int i=0 ; i<=n ; i++)
    {
        if( s[i]=='0' ) continue ;

        int l = i , r= i ;
        while( r+1 <=n && s[r] == s[r+1] ) r++ ;

        if( r-l+1 >= m )
        {
            printf("-1\n") ;
            return 0 ;
        }

        i = r ;
    }

    dp[n] = 0 ;
    dq.push_back( mp(0,n) ) ;

    for(int i=n-1 ; i>=0 ; i--)
    {
        if( dq.front().yy > i+m ) dq.pop_front() ;

        if( s[i]=='1' )
        {
            dp[i] = n + 100 ;
        }
        else{
            dp[i] = dq.front().xx + 1 ;
        }
        while( dq.size() > 0 && dp[i] <= dq.back().xx ) dq.pop_back() ;
        dq.push_back( mp( dp[i] , i ) ) ;
    }

//    printf("%d\n",dp[0]) ;

 //   for(int i=0 ; i<=n ; i++) printf("%d ",dp[i]) ;
 //   printf("\n") ;

//    DBG ;

    vector <int> ans ;

    for(int i=0 ; i<n ; i++)
    {
        int l = i+1 ;
        while( dp[l] != dp[i]-1 ) l++ ;
        ans.pb( l-i ) ;
        i = l-1 ;
   //     printf("%d\n",i) ;
    }

//    DBG ;

    for( auto val:ans ) printf("%d ",val) ;
    printf("\n") ;

    return 0 ;
}


Measured memory_bytes: 1404
#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<string> vec;
int H, W;

void compress_row(string& s)
{
	int i;
	for (i = 0; i < (int)s.size(); i++) {
		if (s[i] == '#') {
			return;
		}
	}

	for (i = 0; i < (int)s.size(); i++) {
		s[i] = '-';
	}
}

bool compress() {

	bool dirty = false;
	auto it = vec.begin();
	while (it != vec.end()) {
		compress_row(*it);
		++it;
	}

	int i;
	for (i = 0; i < W; i++) {
		bool able = true;
		int j;
		for (j = 0; j < (int)vec.size(); j++) {
			if (vec[j][i] == '#') {
				able = false;
				break;
			}
		}	

		if (!able) {
			continue;
		}

		dirty = true;
		for (j = 0; j < (int)vec.size(); j++) {
			vec[j][i] = '-';
		}
	}

	return dirty;
}

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

	string s;
	for (int i = 0; i < H; i++) {
		cin >> s;
		vec.push_back(s);
	}

	compress();

	for (int i = 0; i < H; i++) {
		bool out = false;
		for (int j = 0; j < W; j++) {
			if (vec[i][j] != '-') {
				cout << vec[i][j];
				out = true;
			}
		}
		if (out) {
			cout << endl;
		}
	}

	return 0;
}


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

using namespace std;

using ll = long long;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    long double L;
    cin >> L;
    L /= 3;
    cout << fixed << setprecision(15) << L * L * L << "\n";
    return 0;
}

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

int main(){
  int n=0;
  char op[4];
  scanf("%s", op);
  for (int i=0; i<4; i++){
    if (op[i]=='+') n++;
    else if (op[i]=='-') n--;
  }
  printf("%d", n);
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
void solve(std::string S){
    bool s1 = S[0] == 'R';
    bool s2 = S[1] == 'R';
    bool s3 = S[2] == 'R';
    if( s1 && s2 && s3){
      cout << 3 << endl;
    } else if(s2 && (s1 || s3)){
      cout << 2 << endl;
    } else {
      cout << (int) (s1 || s2 || s3) << endl;
    }
}
 
int main(){
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


Measured memory_bytes: 3584
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<set>
#include<vector>
#include<bitset>
#include<map>
#define N 100005
#define ll long long
#define oo 100000000
#define For(i,x,y) for(int i=x;i<=y;i++)
#define Rep(i,x,y) for(int i=x;i>=y;i--)
#define Forn(i,x,y) for(int i=x;i<y;i++)
using namespace std;
inline int read(){int x=0,f=0;char ch=getchar();for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-48;return f?-x:x;}
inline void write(int x){if(x<10) putchar(x+48);else write(x/10),putchar(x%10+48);}
inline void writeln(int x){if(x<0) putchar('-'),x=-x;write(x);putchar('\n');}
int n,a[N],p[N];
int main(){
	n=read();For(i,1,n) a[i]=read();
	For(i,1,n){
		if(a[i]>0) p[a[i]-1]++;
		p[a[i]]++;
		p[a[i]+1]++;
	}
	int mx=0;
	For(i,0,100000) mx=max(mx,p[i]);
	writeln(mx);
	return 0;
}

Measured memory_bytes: 1024
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
mx = max([abs(x) for x in a])
p = [i for i in range(n) if abs(a[i])==mx][0]
seq = []
if a[p]>0:
    for i in range(1,n):
        while a[i-1]>a[i]:
            a[i] += a[p]
            seq.append((p,i))
        if a[i]>a[p]:
            p = i
elif a[p]<0:
    for i in range(n-2,-1,-1):
        while a[i]>a[i+1]:
            a[i] += a[p]
            seq.append((p,i))
        if a[i]<a[p]:
            p = i
print(len(seq))
for a,b in seq:
    print("{} {}".format(a+1,b+1))


Measured memory_bytes: 38488
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<n;++i)
#define rep2(i,a,b) for (ll i=a;i<b;++i)
const ll MOD=1000000007;
const ll INF=1e9;
const ll IINF=1e18;
const double EPS=1e-8;
const double pi=acos(-1);

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

int main(){
    int N;
    cin >> N;
    map<int,int> m;
    rep(i,N){
        int a;
        cin >> a;
        m[a]=i;
    }
    int sum=0;
    ll ans=0;
    for (auto x:m){
        if ((x.second-sum)%2!=0){
            ans++;
        }
        sum++;
    }
    cout << ans/2 << endl;
}

Measured memory_bytes: 4992
import java.util.*;
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 ab = Math.max(a,b);
      int max = Math.max(ab,c);
      System.out.println(max*10+a+b+c-max);
      sc.close();
    }
}

Measured memory_bytes: 23124
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <set>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
#include <iomanip>
#include <numeric>

using namespace std;

typedef long long ll;

#define forn(i,n) for(int i = 0; i < int(n);++i)
#define pb push_back
#define vi vector<int>
#define vb vector<bool>
#define vll vector<ll>
#define sz(x) (int)x.size()

void solve(){

}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    /* ll t;
    cin >> t;
    while(t--){
    	solve();
    }*/
    ll n;
    cin >> n;
    if( n > 82){
        cout << "No";
        return 0;
    }
    int a;
    for(int i = 1; i <= 9; ++i){
        a = n/i;
        if( a * i == n && a < 10){
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<numeric>
#include<vector>
#include<set>
#include<map>
using namespace std;

int main(){
  int a[3];
  for(int i=0;i<3;i++) cin >> a[i];
  int count = 1000000;
  int count_;
  int b,c;
  for(int i=0;i<3;i++){
    count_ = 0;
    b = a[(i+1)%3] - a[i];
    c = a[(i+2)%3] - a[i];
    if(b >= 0) count_ += b;
    else count_ += (-1*b+1)/2-b%2;
    if(c >= 0) count_ += c;
    else count_ += (-1*c+1)/2-c%2;
    count = min(count,count_);
  }
  cout << count << endl;
  return 0;
}


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

int main(){
	
	int store;

	cin >> a >> bb;

	string c = to_string(bb);
	string b1, b2;

	int d = c.size();

	for(int i=0;i<d;i++){
		if(c[i]=='.'){
            store = i;
			break;
		}
		b1 = b1 + c[i];
	}

	for(int i = store+1; i<d; i++){
		b2 = b2 + c[i];
		if( b2.size() == 2 ){
			break;
		}
	}

	ll bb1 = stoi(b1);
	ll bb2 = stoi(b2);
	bb1 = bb1*100 + bb2;

	cout << a*bb1/100 << endl;

    return 0;
}


Measured memory_bytes: 3752
N = int(input())
A = sorted([(int(a), i) for i, a in enumerate(input().split())], key = lambda x: x[0])[::-1]
X = [0] + [-1<<100] * (N + 1)
for k, (a, i) in enumerate(A):
    nX = [0] * (N + 2)
    for j in range(k + 1):
        nX[j] = max(nX[j], X[j] + abs(N - (k - j) - 1 - i) * a)
        nX[j+1] = max(nX[j+1], X[j] + abs(j - i) * a)
    X = nX
print(max(X))

Measured memory_bytes: 68924
#include<iostream>
#include<string>
#define int long long
using namespace std;
char s1[110],s2[110];
int n;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s1[i];
	}
	for(int i=1;i<=n;i++){
		cin>>s2[i];
	}
	for(int i=1;i<=n;i++){
		cout<<s1[i]<<s2[i];
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int MAX = 100000;
/* global variables */
int N;
vector<vector<int> > G(MAX, vector<int>());
map<pii, int> mp;
int max_color = 0;
/* function */
void bfs() {
    queue<pii> q;
    q.push(pii(0, 0));
    vector<int> visited(MAX, 0);
    visited[0] = 1;
    while (!q.empty()) {
        pii tmp = q.front(); q.pop();
        int from = tmp.first, color = tmp.second;
        int next_color = 1;
        for (auto to : G[from]) {
            if (visited[to]) continue;
            visited[to]= 1;
            if (next_color == color) next_color++;
            mp[make_pair(from, to)] = next_color;
            q.push(pii(to, next_color));
            max_color = max(max_color, next_color);
            next_color++;
        }
    }
}
/* main */
int main(){
    cin >> N;
    int u, v;
    vector<pii> vp;
    for (int i = 0; i < N - 1; i++) {
        cin >> v >> u;
        v--; u--;
        G[u].push_back(v);
        G[v].push_back(u);
        vp.push_back(pii(v, u));
    }
    bfs();
    cout << max_color << '\n';
    for (auto p : vp) {
        cout << mp[p] << '\n';
    }
}


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

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

    ll MOD = pow(10, 9) + 7;

    map<char, ll> cnt;
    rep(i, N) { cnt[S[i]]++; }

    ll res = 1;
    for (auto p : cnt)
        res *= (p.second + 1), res %= MOD;
    cout << res - 1 << endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int main() {
    string S, T; cin >> S >> T;
    S += S;
    for (int i = 0; i < S.length() - T.length(); ++i) {
        string str = S.substr(i, T.length());
        if (str == T) {
            printf("%s\n", "Yes"); return 0;
        }
    }
    printf("%s\n", "No");
    return 0;
}


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


int main()
{
	char S[20];
	int i;


	fgets(S, sizeof(S), stdin);
	//S[strlen(S) - 1] = '\0';

	for(i = 0; i < strlen(S); i++){
		if(S[i] == ',')
			printf(" ");
		else
			printf("%c", S[i]);
	}

	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#define ll long long int
using namespace std;
ll N,M;
int main()
{
	cin>>N>>M;
	if (N==1&&M!=1)cout<<M-2<<endl;
	else if (M==1&&N!=1)cout<<N-2<<endl;
	else if (N==1&&M==1)cout<<1<<endl;
	else cout<<(N-2)*(M-2);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <bitset>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
 
using namespace std;
typedef long long ll;
 
int main(){
  ll A,B,N;
  cin >> A >> B >> N;

  if(B<=N){
    cout << A*(B-1)/B << endl;
  }else{
    cout << A*(N%B)/B << endl;
  }

  return 0;
}


Measured memory_bytes: 3636
#include<iostream>
#include<queue>
#include<map>
#include<vector>
#include<string>

using namespace std;


int main()
{
	int n, q, time, now = 0;
	string name;
	map<string, int> data;
	vector<map<string, int> > so;
	queue<map<string, int> > si;

	cin >> n >> q;

	for (int i = 0; i != n; ++i)
	{
		cin >> name >> time;
		data[name]=time;
		si.push(data);
		data.clear();
	}
	

	while (1)
	{
		if (si.empty())
		{
			break;
		}

		if ((si.front().begin())->second > q)
		{
			now += q;
			(si.front().begin())->second -= q;
			si.push(si.front());
			si.pop();
		}
		else
		{
			now+=(si.front().begin())->second;
			(si.front().begin())->second = now;
			so.push_back(si.front());
			si.pop();
		}
	}

	for (int i = 0; i != so.size(); ++i)
	{
		cout << so.at(i).begin()->first << " " << so.at(i).begin()->second << endl;
	}

	return 0;

}


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

#define fo(i, n) for(int i=0; i<n; i++)
#define Fo(i, k, n) for(int i=k; i<n; i++)
#define endl "\n"

int dp[3002][3002];

int main() {

	string a, b;
	cin >> a >> b;

	int al = a.length(), bl = b.length(), find;
	fo(i, al + 1) fo(j, bl + 1) dp[i][j] = 0;

	Fo(i, 1, al + 1)
	Fo(j, 1, bl + 1) {
		dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		if (a[i - 1] == b[j - 1]) {
			dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
		}
	}

	find = dp[al][bl];
	int i = al, j = bl;
	char ans[find + 1];
	ans[find] = '\0';

	while (i > 0 && j > 0) {
		if (a[i - 1] == b[j - 1]) {
			ans[find - 1] = a[i - 1];
			find--;
			j--;
			i--;
		} else if (dp[i - 1][j] < dp[i][j - 1]) {
			j--;
		} else {
			i--;
		}
	}

	cout << ans;

	return 0;
}

Measured memory_bytes: 38784
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define p_b push_back
#define MOD 1000000007
ll ncr[2005][2005];
void NCR()
{
    ll i,j;
    for(i=0;i<2005;i++)
    {

        ncr[i][0] = 1;
        ncr[i][i] = 1;

        for(j=1;j<i;j++)
        {
            ncr[i][j] = ncr[i-1][j] + ncr[i-1][j-1];
            ncr[i][j] %= MOD;


        }
    }

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

    ll n,k;
    cin >> n >> k;
    ll i;
    NCR();

    for(i=1;i<=k;i++)
    {

        if(i> (n-k+1))
        {

            cout << 0 << endl;
            continue;
        }
        else
        {

            ll temp = (ncr[n-k+1][i] * ncr[k-1][i-1]) %MOD ;
            cout << temp << endl;

        }
    }



    return 0;
}


Measured memory_bytes: 30208
///スマホコーディング
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int n; 
  double t,a;
  cin>>n>>t>>a;
  double minv=1e9;
  int idx=0;
  for(int i=1;i<=n;i++){
    double h;
    cin>>h;
    if(abs(t-h*0.006-a)<minv){
      minv=abs(t-h*0.006-a);
      idx=i;
    }
  }
  cout<<idx<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define vll vector<ll>
#define pii pair<ll,ll>
#define vvll vector< vector<ll> >
#define pb push_back
#define sz(v) (ll)(v).size()
#define inf 1e18
#define md 1000000007
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define tel(a){cout<<a<<"\n";}
#define tell(a,b){cout<<a<<" | "<<b<<"\n";}
#define telll(a,b,c){cout<<a<<" | "<<b<<" | "<<c<<"\n";}
#define teln(v,n){cout<<"v- ";rep(o,0,n)cout<<v[o]<<" ";cout<<"\n";}
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

#define M 200010


int main(){
    IOS;
 	
 	ll n,k;cin>>n>>k;
 	ll a[n];
 	rep(i,0,n)cin>>a[i];
 	vector<pair<ld,ll>>v;
 	ll d=0;
 	rep(i,0,n){
 		if(!a[i]){d++;continue;}
 		ld x=log2(abs(a[i]));
 		v.pb({x,i});
 	}
 	if(n-d<k){
 		cout<<"0";
 		return 0;
 	}
 	sort(all(v));
 	reverse(all(v));
 	ll ok=1;
 	rep(i,0,k){
 		if(a[v[i].se]<0)ok*=-1;
 	}
 	if(k==n){
 		if(d)cout<<0;
 		else {
	 		ll ans=1;
	 		rep(i,0,n)(ans*=a[i])%=md,(ans+=md)%=md;
	 		cout<<ans;
 		}
 		return 0;
 	}
 	if(ok==1){
 		ll ans=1;
 		rep(i,0,k)(ans*=a[v[i].se])%=md,(ans+=md)%=md;
 		cout<<ans;
 		return 0;
 	}
 	ld x=0;
 	ll cnt=0;
 	rep(i,0,k)if(a[v[i].se]<0)cnt++;
 	ll ans=1,c=0;
 	rep(i,0,k){
 		if(a[v[i].se]<0){
 			c++;
 			if(c==cnt)continue;
 		}
 		(ans*=a[v[i].se])%=md,(ans+=md)%=md;
 		x+=v[i].fi;
 	}
 	if(!cnt)x=-1e9;
	ok=0;
 	rep(i,k,sz(v)){
 		if(a[v[i].se]>0){	 ok=1;
	 		(ans*=a[v[i].se])%=md,(ans+=md)%=md;
	 		x+=v[i].fi; break;
 		}
 	}
 	if(!ok)x=-1e9;
 	ld y=0;
 	ll cnt1=0;
 	rep(i,0,k)if(a[v[i].se]>0)cnt1++;
 	ll ans1=1;c=0;
 	rep(i,0,k){
 		if(a[v[i].se]>0){
 			c++;
 			if(c==cnt1)continue;
 		}
 		(ans1*=a[v[i].se])%=md,(ans1+=md)%=md;
 		y+=v[i].fi;
 	}
 	if(!cnt1)y=-1e9; ok=0;
 	rep(i,k,sz(v)){
 		if(a[v[i].se]<0){	 ok=1;
	 		(ans1*=a[v[i].se])%=md,(ans1+=md)%=md;
	 		y+=v[i].fi; break;
 		}
 	}
 	if(!ok)y=-1e9;
 	if(x<0 and y<0){
 		if(d){
 			cout<<"0";
 			return 0;
 		}
 		ans=1;
 		reverse(all(v));
 		rep(i,0,k)(ans*=a[v[i].se])%=md,(ans+=md)%=md;
 		cout<<ans;
 	}
 	else if(x<y)cout<<ans1;
 	else cout<<ans;
    return 0;
}

Measured memory_bytes: 13308
#include <iostream>
#include<algorithm>
using namespace std;
int d[551][551];
int tr[551][551];
int n,m,q;
void updata(int x,int y)
{
	int t;
	while(x>0)
	{
		t=y;
		while(t<=n)
		{
			d[x][t]++;
			t+=t&-t;
		}
		x-=x&-x;
	}
}
int que(int x,int y)
{
	int sum=0;
	int t;
	while(x<=n)
	{
		t=y;
		while(t>0)
		{
			sum+=d[x][t];
			t-=t&-t;
		}
		x+=x&-x;
	}
	return sum;
}
int main(int argc, char *argv[])
{
	cin>>n>>m>>q;
	int a,b;
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b;
		updata(a,b);
	}
	for(int i=0;i<q;i++)
	{
		cin>>a>>b;
		cout<<que(a,b)<<endl;
	}
	return 0;
}

Measured memory_bytes: 2048
#include<bits/stdc++.h>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define rrep(i,a) for(int i=(int)a-1;i>=0;--i)
#define REP(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RREP(i,a,b) for(int i=(int)a-1;i>=b;--i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
typedef std::vector<int> vi;
typedef std::vector<std::vector<int>> vvi;
typedef std::vector<long long> vl;
typedef std::vector<std::vector<long long>> vvl;
#define out(x) cout<<x<<"\n";
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}


ll gcd(ll n, ll m) {
    ll tmp;
    while (m!=0) {
        tmp = n % m;
        n = m;
        m = tmp;
    }
    return n;
}
 
ll lcm(ll n, ll m) {
    return abs(n) / gcd(n, m)*abs(m);//gl=xy
}

using namespace std;

ll dp[55][2550];
vector<int> c;
vector<ll>d;
int n, m;
ll s;

template<typename T>
struct edge{
  int to;
  T cost;
  edge(int to,T cost):to(to),cost(cost){}
};


template<typename T>
vector<vector<ll>> dijkstra(vector<vector<edge<T>>> &g){//sは始点
  const auto INFTY=numeric_limits<ll>::max()/2;//2回以上使うときはオーバーフローに気をつける(INFTYのときはif文で弾くなど)
  vector<vector<ll>> dist(n, vector<ll>(2505, INFTY));
  using P = pair<T, int>; //firstは最短距離,secondは頂点の番号
  const int MAXV = 2500;
  priority_queue<P, vector<P>, greater<P>> pq;
  dist[0][s] = 0;
  pq.emplace(T{dist[0][s],s},0);
  //first.first:時間,first.second:銀貨,secod:頂点
  while(!pq.empty()){
    auto x=pq.top();pq.pop();
    int v = x.second;
    int silver = x.first.second;
    ll time = x.first.first;
    if (dist[v][silver] <time){
      continue;   //最短距離でなければ飛ばす
    }
    if(silver+c[v]<=MAXV){
      if(chmin(dist[v][silver+c[v]],time+d[v])){
        pq.emplace(T{dist[v][silver + c[v]], silver + c[v]}, v);
      }
    }
    for(auto e:g[v]){
      if((silver-e.cost.second>=0)&&(chmin(dist[e.to][silver-e.cost.second],dist[v][silver]+e.cost.first))){
        pq.emplace(T{dist[e.to][silver-e.cost.second],silver-e.cost.second},e.to);
      }
    }
  }
  return dist;
}

using P = pair<ll, ll>;
void solve()
{
	cin >> n >> m >> s;
  chmin(s, 2500LL);
  vector<vector<edge<P>>> g(n);
  rep(i,m){
		int u, v;
		ll a, b;
		cin >> u >> v >> a >> b;
		u--;
		v--;
    g[u].eb(v, P{b, a});
    g[v].eb(u, P{b, a});
  }
  c.resize(n);
  d.resize(n);
  rep(i,n){
    cin >> c[i] >> d[i];
    chmin(c[i], 2500);
  }
  auto e = dijkstra(g);
  REP(i,1,n){
    ll ans = INF;
    rep(j, 2501)
    {
      chmin(ans, e[i][j]);
    }
    cout << ans << "\n";
  }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(15);
    solve();
    return 0;
}


Measured memory_bytes: 7244
#include<stdio.h>
int main(void)
{
	int n;
	int k;
	int i;
	int sum=0;

	scanf("%d", &n);
	scanf("%d", &k);
	sum = n - k;

	if (k == 1) {
		sum = 0;
	}
	printf("%d\n", sum);

	return 0;
}

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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define all(x) (x).begin(),(x).end()
#define endl "\n"

using ll = long long;
using P = pair<int,int>;
using mp =  map<string,int>;

const int MOD = 1e9 + 7;
const int INF = 1001001001;


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

    int h, w;
    cin >> h >> w;
    vector<vector<char>> a(h, vector<char>(w));

    rep(i, h){
        rep(j, w){
            cin >> a[i][j];
        }
    }

    rep(i, w+2) cout << '#';
    cout << endl;
    rep(i, h){
        cout << '#';
        rep(j, w){
            cout << a[i][j];
        }
        cout << '#' << endl;
    }
    rep(i, w+2) cout << '#';
    cout << endl;


    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
n  = int(input())
#  = map(int, input().split())
#  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

if str(n)[-1] == '3':
    print('bon')
elif str(n)[-1] in ['2', '4', '5', '7', '9']:
    print('hon')
else:
    print('pon')


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;

static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const ll INF = 1023456789;

#define REP(i,n)	for(int i=0;i<n;++i)
#define REPR(i,n)	for(int i=n-1;i>=0;--i)
#define FOR(i,s,n)	for(int i=s;i<n;++i)
#define FORR(i,s,n)	for(int i=n-1;i>=s;--i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define F			first
#define S			second

ll n, d;
ll s[10];
ll solve(ll i, ll l) {
	if (i < l) {
		ll res = 0;
		s[i] = 3;
		res += solve(i+1, l);
		s[i] = 5;
		res += solve(i+1, l);
		s[i] = 7;
		res += solve(i+1, l);
		return res;
	}
	bool f3 = false, f5 = false, f7 = false;
	REP(i, l) {
		f3 |= (s[i] == 3);
		f5 |= (s[i] == 5);
		f7 |= (s[i] == 7);
	}
	if (!f3 || !f5 || !f7) return 0;
	if (l < d) return 1;
	ll v = 0;
	REP(i, l) v = v*10 + s[i];
	return (v <= n ? 1 : 0);
}

int main(int argc, char **argv) {
	cin >> n;
	d = 0;
	for (ll i = n; i > 0; i /= 10) ++d;
	ll res = 0;
	FOR(i, 1, d+1) res += solve(0, i);
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 3640
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int n;

int main(){
  auto dmy=scanf("%d", &n);
  vector<int> l(n);
  for(int i=0; i<n; i++) dmy=scanf("%d", &l[i]);
  sort(l.begin(), l.end());
  int ans=0;
  for(int i=0; i<n-2; i++){
    for(int j=i+1; j<n-1; j++){
      int count;
      vector<int> vec(l.begin()+j+1, l.begin()+n);
      int min_c=l[j]-l[i];
      int max_c=l[i]+l[j];
      if(min_c < l[n-1]){
        auto iter=upper_bound(vec.begin(), vec.end(), min_c);
        count = vec.end()-iter;
        ans += count;
        if(max_c <= l[n-1]){
          iter=lower_bound(vec.begin(), vec.end(), max_c);
          ans -= (vec.end()-iter);
        }
      }
    }
  }
  printf("%d\n", ans);
}



Measured memory_bytes: 256
// TOPSIC001_0

#include <bits/stdc++.h>

using namespace std;

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

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int main(){
    int A,B; cin >> A >> B;

    if(B % A == 0) cout << A + B;
        else cout << B - A;

    return 0;
//    cout << S.substr(0,4) << endl;
//    cout << S.substr(5,2) << endl;
//    cout << S.substr(8,2) << endl;
}

Measured memory_bytes: 256
A, B = tuple(input().split())



def strength(nchr):
    if nchr == '2':
        return 0
    elif nchr == '3':
        return 1
    elif nchr == '4':
        return 2
    elif nchr == '5':
        return 3
    elif nchr == '6':
        return 4
    elif nchr == '7':
        return 5
    elif nchr == '8':
        return 6
    elif nchr == '9':
        return 7
    elif nchr == '10':
        return 8
    elif nchr == '11':
        return 9
    elif nchr == '12':
        return 10
    elif nchr == '13':
        return 11
    elif nchr == '1':
        return 12

st_a = strength(A)
st_b = strength(B)
if st_a > st_b:
    print('Alice')
elif st_a < st_b:
    print('Bob')
else:
    print('Draw')



Measured memory_bytes: 3064
#include <algorithm>
#include <bits/stdc++.h>
#include <bitset>
#include <cassert>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <math.h>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
#define REP(i, n) for (int64_t i = 0; i < (int64_t)n; i++)
#define REP_FOR(i, a, b) for (int64_t i = (int64_t)a; i < (int64_t)b; i++)
#define REP_REV(i, a, b) for (int64_t i = (int64_t)a; i > (int64_t)b; i--)
#define FORALL(v) (v).begin(), (v).end()
#define mp(a, b) make_pair(a, b)
#define eb(x) emplace_back(x)
#define F first
#define S second
typedef long long ll;
typedef long double ld;
typedef pair<int64_t, int64_t> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int64_t> vii;
typedef vector<vii> vvii;
const ll mod = 1e9 + 7;
const int64_t infi = 1147483600;
const ll infl = 4e18 + 5;
const char EOL = '\n';
//cout << fixed << setprecision(17) << res << endl;
const ll MOD = 998244353;

int main() {
    string s;
    cin >> s;
    auto n = s.length();
    bool res = true;
    auto l = n / 2;
    for (ll i = 0; i < l; ++i) {
        if (s[i] != s[n-1-i]) {
            cout << "No" << endl;
            return 0;
        }
    }
    auto nn = (n-1)/2;
    l = nn /2;
    for (ll i = 0; i < l; ++i) {
        if (s[i] != s[nn-1-i]) {
            cout << "No" << endl;
            return 0;
        }
    }
    auto m = (n+3)/2;
    for (ll i = 0; i + m-1< n; ++i) {
        if (s[i + m-1] != s[n-1-i]) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;


}


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

typedef long long ll;

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

#define FOR(i, start, end) for(ll i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)

int main(void) {
    ll A, B, C, X, Y;
    cin >> A >> B >> C >> X >> Y;
    
    ll ans = LLONG_MAX;
    FOR(i, 0, 100001) {
        ans = min(ans, 2 * C * i + max(X - i, 0LL) * A + max(Y - i, 0LL) * B);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256