akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>

using namespace std;

#define mod 1000000007

int main()
{
	int n, k;
	while(1){
		cin >> n >> k;
		if(n == 0) break;
		vector<int> v;
		int wp = 0;
		for(int i = 0; i < k; i++){
			int a;
			cin >> a;
			if(a == 0) wp++;
			else v.push_back(a);
		}
		// cout << endl;
		sort(v.begin(), v.end());
		for(int i = 0; i < v.size(); i++){
			// cout << v[i] << " ";
		}
		// cout << endl;
		// cout << v.size() << endl;
		vector<pair<int, int> > renzoku;
		for(int i = 0; i < v.size(); i++){
			int cnt = 1;
			while(i + cnt < v.size() && v[i + cnt] - v[i + cnt - 1] == 1) cnt++;
			renzoku.push_back(make_pair(v[i], cnt));
			i += cnt - 1;
		}
		int ans = renzoku[0].second;
		int nowwp = wp;
		int cnt = 1;
		while(cnt < renzoku.size() && renzoku[cnt].first - renzoku[cnt - 1].first - renzoku[cnt - 1].second <= nowwp){
			int tmp = renzoku[cnt].first - renzoku[cnt - 1].first - renzoku[cnt - 1].second;
			nowwp -= tmp;
			ans += tmp + renzoku[cnt].second;
			cnt++;
		}
		int result = ans;
		ans += nowwp;
		for(int i = 1; i < renzoku.size(); i++){
			// cout << renzoku[i].first << " " << renzoku[i].second << endl;
			if(cnt == 1){
				result = renzoku[i].second;
			} else {
				nowwp += renzoku[i].first - renzoku[i - 1].first - renzoku[i - 1].second;
				result -= renzoku[i].first - renzoku[i - 1].first;
				cnt--;
			}
			while(i + cnt < renzoku.size() && renzoku[i + cnt].first - renzoku[i + cnt - 1].first - renzoku[i + cnt - 1].second <= nowwp){
				int tmp = renzoku[i + cnt].first - renzoku[i + cnt - 1].first - renzoku[i + cnt - 1].second;
				nowwp -= tmp;
				result += tmp + renzoku[i + cnt].second;
				cnt++;
			}
			// cout << renzoku[i].first << " " << renzoku[i].second << " " << result << endl;
			ans = max(ans, result + nowwp);
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 3412
import sys
input = sys.stdin.readline
import math


# 持っているビスケットを叩き、1枚増やす
# ビスケット A枚を 1円に交換する
# 1円をビスケット B枚に交換する
def main():
    s = str(input()).strip()
    n = len(s)
    cnt = 0
    ans = [0] * n
    for i, moji in enumerate(s):
        if moji == "R":
            cnt += 1
            continue
        else:
            even_num = cnt//2
            odd_num = cnt - even_num
            ans[i] += even_num
            ans[i-1] += odd_num
            cnt = 0
    cnt = 0
    for i in range(n-1, -1, -1):
        if s[i] == "L":
            cnt += 1
            continue
        else:
            even_num = cnt // 2
            odd_num = cnt - even_num
            ans[i] += even_num
            ans[i+1] += odd_num
            cnt = 0
    print(*ans)

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)


def input_list():
    return list(map(int, input().split()))


def input_list_str():
    return list(map(str, input().split()))


if __name__ == "__main__":
    main()


Measured memory_bytes: 78324
object Main {
  def main(args: Array[String]): Unit = {
    import scala.io.StdIn.readLine
    val Array(datN) = readLine.split(" ").map(_.toInt)
    val datA = readLine.split(" ").map(_.toInt)

    var money = 1000L;
    var stock = 0L;
    var price = 0;

    (0 until datN - 1) foreach {i =>
      if (stock == 0) {
        if (datA(i + 1) > datA(i)) {
          stock = (money / datA(i)).toLong
          money -= datA(i) * stock
          price = datA(i)
        }
      } else {
        if (datA(i + 1) < datA(i)) {
          money += datA(i) * stock
          stock = 0
          price = 0
        }
      }
    }

    if (stock != 0) {
      if (datA.last > price) money += stock * datA.last
      else money += stock * price
    }

    println(money)
  }
}


Measured memory_bytes: 54852
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String X = sc.next();
		String ans1 = "ABC";
		String ans2 = "ARC";

		if(X.contentEquals(ans1)) {
			System.out.println(ans2);
		}else {
			System.out.println(ans1);
		}
	}
}


Measured memory_bytes: 35676
n = 4
total = int(0)
zenhan = int(0)
kouhan = int(0)

N, K, X, Y = [int(input()) for i in range(4) ]

kouhan = (N - K ) * Y

if (N > K):
    zenhan = K * X
    total = zenhan + kouhan
else:
    zenhan = N * X
    total = zenhan

print(total)

Measured memory_bytes: 9096
#include <iostream>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <iomanip>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <functional>
/* Data Structure */
#include <vector>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <stack>
#include <queue>

using namespace std;

#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3fLL
#define debug cerr << "======= GOT_HERE ======\n"
#define endl "\n"

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef map<int,int> mii;
typedef map<long long,long long> mll;
typedef set<int> si;
typedef set<long long> sll;

long long n,k;

set<int> s;

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	s.clear();
	cin>>n;
	for(int i=0;i<n;++i)
	{
		cin>>k;
		s.insert(k);
	}
	if(s.size()==n)
	{
		cout << "YES" << endl;
	}
	else
	{
		cout << "NO" << endl;
	}
	return 0;
}

Measured memory_bytes: 9600
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
  int x,a,b; cin>>x>>a>>b;
  if(abs(x-a)<abs(x-b)) cout<<"A"<<endl;
  else cout<<"B"<<endl;
}

Measured memory_bytes: 256
#pragma gcc optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5 + 10;

string s;
ll a[N], ans;

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> s;
    s = '>' + s + '<';
    for (int i = 0; i < s.size() - 1;) {
        if (s[i] == '>' && s[i + 1] == '<') {
            a[i++] = 0;
            while (i < s.size() - 1 && s[i] == '<') a[i] = max(a[i], a[i - 1] + 1), ++i;
        }
        else ++i;
    }
    // for (int i = 0; i < s.size() - 1; ++i)
    //     cout << a[i] << ' '; cout << '\n';
    for (int i = s.size() - 2; i >= 0;) {
        if (s[i] == '>' && s[i + 1] == '<') {
            --i;
            while (i >= 0 && s[i] == '>') a[i] = max(a[i], a[i + 1] + 1), --i;
            if (i >= 0) a[i] = max(a[i], a[i + 1] + 1), --i;
        }
        else --i;
    }
    for (int i = 0; i < s.size() - 1; ++i)
        ans += a[i];
    cout << ans << '\n';
}

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

typedef vector<int> vint;

int imos[100][100][100];

vint compress2(vint v1, const vint &v2){
	v1.insert(v1.end(), v2.begin(), v2.end());
	sort(v1.begin(), v1.end());
	v1.erase(unique(v1.begin(), v1.end()), v1.end());
	return v1;
}

int index(const vint &v, int x){
	return lower_bound(v.begin(), v.end(), x) - v.begin();
}

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

	vint x1(n), x2(n), y1(n), y2(n), z1(n), z2(n);
	for(int i = 0; i < n; ++i){
		cin >> x1[i] >> y1[i] >> z1[i] >> x2[i] >> y2[i] >> z2[i];
	}

	vint xs = compress2(x1, x2);
	vint ys = compress2(y1, y2);
	vint zs = compress2(z1, z2);

	for(int i = 0; i < n; ++i){
		int xi1, yi1, zi1, xi2, yi2, zi2;
		xi1 = index(xs, x1[i]);
		yi1 = index(ys, y1[i]);
		zi1 = index(zs, z1[i]);
		xi2 = index(xs, x2[i]);
		yi2 = index(ys, y2[i]);
		zi2 = index(zs, z2[i]);

		++imos[xi1][yi1][zi1];
		--imos[xi1][yi2][zi1];
		--imos[xi2][yi1][zi1];
		++imos[xi2][yi2][zi1];
		--imos[xi1][yi1][zi2];
		++imos[xi1][yi2][zi2];
		++imos[xi2][yi1][zi2];
		--imos[xi2][yi2][zi2];
	}

	for(int i = 1; i < xs.size(); ++i)
	for(int j = 0; j < ys.size(); ++j)
	for(int k = 0; k < zs.size(); ++k){
		imos[i][j][k] += imos[i-1][j][k];
	}

	for(int i = 0; i < xs.size(); ++i)
	for(int j = 1; j < ys.size(); ++j)
	for(int k = 0; k < zs.size(); ++k){
		imos[i][j][k] += imos[i][j-1][k];
	}

	for(int i = 0; i < xs.size(); ++i)
	for(int j = 0; j < ys.size(); ++j)
	for(int k = 1; k < zs.size(); ++k){
		imos[i][j][k] += imos[i][j][k-1];
	}

	long long ans = 0;
	for(int i = 0; i < xs.size(); ++i)
	for(int j = 0; j < ys.size(); ++j)
	for(int k = 0; k < zs.size(); ++k){
		if(imos[i][j][k] >= m){
			ans += (long long)(xs[i+1] - xs[i]) * (ys[j+1] - ys[j]) * (zs[k+1] - zs[k]);
		}
	}
	
	cout << ans << '\n';
}

Measured memory_bytes: 5120
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x, k, d, ans;
int main()
{
	cin >> x >> k >> d;
	ll a = abs(x) / d;
	if (a == k)
	{
		ans = abs(x) - d * a;
	}
	else if (a < k)
	{
		ll c = k - a;
		if (c & 1)
		{
			ans = d * (a + 1) - abs(x);
		}
		else
		{
			ans = abs(x) - d * a;
		}
	}
	else
	{
		ans = abs(x) - d * k;
	}
	cout << ans << endl;
	return 0;
}


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

int main(){
  int r,g,b;
  cin >> r >> g >> b;
  int num = r*100 + g*10+ b;
  bool ans = (num % 4 == 0 ? true: false);
  if(ans) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) throws Exception {

        InputStreamReader is = new InputStreamReader(System.in);
        BufferedReader reader = new BufferedReader(is);

        List<String> mylist = new ArrayList<>();

        // 標準入力からの値を変数strinputに代入
        String strinput = reader.readLine();

        while (strinput != null) {

            mylist.add(strinput);
            strinput = reader.readLine();

        }

        String arr01[] = mylist.get(0).split(" ");
        String arr02[] = mylist.get(1).split(" ");
        int n = Integer.valueOf(arr01[0]);

        Boolean chkflg = true;

        for (int i = 0; i < n - 2; i++) {
            int temp1 = Integer.valueOf(arr02[i]);
            int temp2 = Integer.valueOf(arr02[i + 1]);
            int temp3 = Integer.valueOf(arr02[i + 2]);

            if (temp1 < temp2) {
                temp2 -= 1;
                arr02[i + 1] = String.valueOf(temp2);

                if (temp2 > temp3) {
                    chkflg = false;
                    break;

                }

            } else if (temp1 == temp2) {
                if (temp2 > temp3) {
                    chkflg = false;
                    break;
                }
            } else {
                chkflg = false;
                break;
            }
        }

        System.out.println(chkflg ? "Yes" : "No");

    }

}


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

string s[2]{
	"RY",
	"GB"
};
int main(){
	int h,w,d;cin>>h>>w>>d;
	rep(i,h){
		rep(j,w){
			int x=i-j,y=i+j;
			int a=(x+2*d*1000)%(2*d),b=(y+2*d*1000)%(2*d);
			printf("%c",s[a>=d][b>=d]);
		}
		puts("");
	}
}

Measured memory_bytes: 512
MOD = 10**9 + 7

n,k=map(int,input().split())
zero_end = min(n,k+1)

inv_mod = [pow(i,MOD-2,MOD) for i in range(zero_end)]

comb_mod1 = [1] * zero_end
comb_mod2 = [1] * zero_end
for i in range(1,zero_end):
    comb_mod1[i] = comb_mod1[i-1] * (n-i+1) * inv_mod[i] %MOD
    comb_mod2[i] = comb_mod2[i-1] * (n-i  ) * inv_mod[i] %MOD

ans = 0

for i in range(zero_end): 
    
    ans = ans + comb_mod1[i] *comb_mod2[i] %MOD
    
print(ans%MOD)

Measured memory_bytes: 28924
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <utility>
#include <complex>
#include <functional>
#include <climits>

using namespace std;
long A[200];
int main() {
    int n, count = 0;
    cin >> n;
    for(int i=0; i<n; i++) {
        cin >> A[i];
    }
    while(true) {
        for(int i=0; i<n; i++) {
            if(A[i] % 2 != 0) {
                cout << count << endl;
                return 0;
            }
            A[i] /= 2;
        }
        count++;
    }
}


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

int main(){
    
    int N;cin>>N;
    int j,k;
    for(int i=1;i<=10000;i++){
        j=i*(i+1)/2;
        if(j>=N){
            k=i;
            break;
        }
    }
    int l=j-N;
    for(int i=1;i<=k;i++){
        if(i!=l) cout<<i<<endl;
    }
    
}




Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//ここから編集する
class Solve {
public:
    void input() {

    }

    void solve() {
        input();
        int N, M;
        cin >> N >> M;
        vector<int> A(N);
        vector<int> B(N + 1); //数字の個数
        vector<int> C(N); // [i, i + 1]が覆っている数
        int blank = 0;  //空白の個数
        rep(i, 0, N) {
            cin >> A[i];
            B[A[i]]++;
            if (A[i] - B[A[i]] >= 0)
                C[A[i] - B[A[i]]]++;
        }
        for (int i = 0; i < N; ++i) blank += !C[i];

        for (int i = 0; i < M; ++i) {
            int x, y;
            cin >> x >> y;
            x--;
            int prev = A[x]; // 変更前の数字
            A[x] = y;

            //prevの分だけ減らす
            if (prev - B[prev] >= 0) {
                C[prev - B[prev]]--;
                if (C[prev - B[prev]] == 0) {
                    blank++;
                }
            }
            B[prev]--;

            //yの文だけ増やす
            B[y]++;
            if (y - B[y] >= 0) {
                C[y - B[y]]++;
                if (C[y - B[y]] == 1) {
                    blank--;
                }
            }

            cout << blank << endl;
        }


    }
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    Solve().solve();


    return 0;
}


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

int main() {
  string s;
  cin>>s;
  rep(i,s.size()){
    if(s[i]=='?'){
      s[i]='D';
    }
  }
  cout<<s<<endl;
}

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

#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
#define rep1(i,s,n) for(long long i=s; i<=(long long)(n);i++)
//rep1は「sからnまで」の繰り返し
#define repr(i,s,n) for(long long i=n;i>=(long long)(s);i--)
//reprは「nからsまで」の繰り返し

typedef long long ll;

const ll inf = 1e18+7;
const ll mod = 1e9+7;


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

    int l=0,r=0;

    vector<int>a(m);
    rep(i,m){
        cin>>a[i];
        if(a[i]<=x)l++;
        else if(a[i]>=x)r++;
    }

    cout<<min(l,r)<<endl;
}



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

int main(){
  int N;
  cin>>N;
  int inc,myno;
  ull SYO=1000000007,sameflg;
  vector<int> C(N,0);
  cin>>C[0];
  int newN=1,jid;//newN
  
  for(int i=1;i<N;i++){
    cin>>inc;
    if (C[newN-1]!=inc){
      C[newN]=inc;
      newN++;
    }
  }
  //Cの数値が何個出現するかを記憶する変数
  vector<int> Cnum(200000,0);
  for(int i=0;i<newN;i++){
    Cnum[C[i]]++;
  }
  vector<int> Cnumsum(200000,0);//参照する最初のindexがこれでわかる
  for(int i=1;i<200000;i++){
    Cnumsum[i]=Cnumsum[i-1]+Cnum[i-1];
  }
  vector<int> Cnumsum_dmy(200000,0);//参照する最初のindexがこれでわかる
  for(int i=0;i<200000;i++){
    Cnumsum_dmy[i]=Cnumsum[i];
  }
  
  //Cの数値が出現したindexを記憶する変数
  vector<int> Cnumid(newN,0);
  for(int i=0;i<newN;i++){
    Cnumid[Cnumsum_dmy[C[i]]]=i;
    Cnumsum_dmy[C[i]]++;
  }
  
  vector<int> sumdp(200000,0);
  
  
  vector<vector<ull>> dp = vector<vector<ull>>(newN, vector<ull>(2, 0));
  ull ans=0;
  dp[0][0]=1;
  sumdp[C[0]]=1;
  for(int i=1;i<newN;i++){
    myno=C[i];
    sameflg=0;
    
    for(int j=0;j<Cnum[myno];j++){
      jid=Cnumid[Cnumsum[myno]+j];
      if (jid>=i){break;}
      //sameflg++;
    }
    
      sameflg+=sumdp[myno];
      sameflg%=SYO;
      dp[i][0]=(dp[i-1][0]+sameflg)%SYO;
      sumdp[myno]=(sumdp[myno]+dp[i-1][0])%SYO;
    
    
  }
    
  ans=dp[newN-1][0];
  cout<<ans%SYO<<endl;
  return 0;
}

Measured memory_bytes: 15872
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
int n,m,ans;
int f[40];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int k;
        cin>>k;
        for(int j=1;j<=k;j++){
            int temp;
            cin>>temp;
            f[temp]++;
        }
    }
    for(int i=1;i<=m;i++){
        if(f[i]==n){ans++;}
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::iter::FromIterator;
#[allow(unused_imports)]
use std::io::stdin;

mod util {
    use std::io::stdin;
    use std::str::FromStr;
    use std::fmt::Debug;

    #[allow(dead_code)]
    pub fn line() -> String {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.trim().to_string()
    }

    #[allow(dead_code)]
    pub fn gets<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|t| t.parse().unwrap())
            .collect()
    }
}

#[allow(unused_macros)]
macro_rules! get {
    ($t:ty) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
                    get!($t)
                   ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
                    get!($($t),*)
                   ).collect::<Vec<_>>()
    };
    ($t:ty ;;) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn main() {
    let s: Vec<char> = util::line().chars().collect();

    if (s.iter().any(|&c| c == 'N') == s.iter().any(|&c| c == 'S'))
        && (s.iter().any(|&c| c == 'W') == s.iter().any(|&c| c == 'E'))
    {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 4352
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np

def main():
	s=input().rstrip().decode('utf-8')
	t=input().rstrip().decode('utf-8')
	slen=len(s)
	tlen=len(t)
	
	dp=[[0]*(slen+1) for _ in range(tlen+1)]
	pr=[[0]*(slen+1) for _ in range(tlen+1)]
	
	
	for i in range(tlen):
		for j in range(slen):
			if s[j]==t[i]:
				dp[i+1][j+1]=dp[i][j]+1
				pr[i+1][j+1]=1
			elif dp[i][j+1]<dp[i+1][j]:
				dp[i+1][j+1]=dp[i+1][j]
				pr[i + 1][j + 1] = 2
			else:
				dp[i+1][j+1]=dp[i][j+1]
				pr[i + 1][j + 1] = 3
	
	ss=slen
	tt=tlen
	ans=""
	while ss>0 and tt>0:
		if pr[tt][ss]==1:
			ans+=s[ss-1]
			tt-=1
			ss-=1
		elif pr[tt][ss]==2:
			ss-=1
		else:
			tt-=1
	print(ans[::-1])
	
	
	
if __name__ == "__main__":
	main()


Measured memory_bytes: 174984
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
n,q=NM()
c=[0]+L()
Q=[L()+[i] for i in range(q)]
Q.sort(key=lambda x:x[1])
ans=[0]*(q)
lastapp=[0 for i in range(n+1)]

No=2**19
BIT=[0]*(No+1)
def addbit(i,x):
    while i<=No:
        BIT[i]+=x
        i+= i&-i
def getsum(i):
    s=0
    while i:
        s+=BIT[i]
        i-= i&-i
    return s
def sumbit(l,r):
    return getsum(r)-getsum(l-1)

j=1
for l,r,i in Q:
    while j<=r:
        t=c[j]
        if lastapp[t]:
            addbit(lastapp[t],-1)
        addbit(j,1)
        lastapp[t]=j
        j+=1
    ans[i]=sumbit(l,r)
print(*ans, sep = "\n")

Measured memory_bytes: 268164
#include <iostream>
#include <algorithm>
#include <string>
#include <iomanip>
#include <complex>
using namespace std;

int main() {
    double x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    double c = abs(x1 - x2) * abs(x1 - x2) + abs(y1 - y2) * abs(y1 -y2);
    c = sqrt(c);
    cout << fixed << setprecision(6) << c << endl;


}



Measured memory_bytes: 3288
import           Control.Monad.ST
import qualified Data.ByteString.Char8        as B
import qualified Data.Vector.Unboxed          as U
import qualified Data.Vector.Algorithms.Radix as U

main :: IO ()
main = do
  [s, w]  <- readInts
  putStrLn $ solve s w

solve :: Int -> Int -> String
solve s w = if w >= s then "unsafe" else "safe"

readInts :: IO [Int]
readInts = map read . words <$> getLine

readIntN :: Int ->  IO (U.Vector Int)
readIntN n = U.unfoldrN n (B.readInt . B.dropWhile ((==) ' ')) <$> B.getLine

radixSort :: U.Vector Int -> U.Vector Int
radixSort xs = runST $ do
  mxs <- U.thaw xs
  U.sort mxs
  U.freeze mxs


Measured memory_bytes: 3768
// Problem : C - HSI
// Contest : AtCoder Regular Contest 085
// URL : https://atcoder.jp/contests/arc085/tasks/arc085_a
// Memory Limit : 256 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define size(x) (int)x.size()

const int N = 1e6 + 1, mod = 1e9 + 7, inf = 2e9;

int n, m;

int main() { cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	int k = 0, t = (n - m) * 100 + 1900 * m;
	double c = 1 << m;
	double ans = 0, p = 1, b = 1.0 - 1.0 / c;
	while (k++ <= N) {
		ans += p * k;
		p *= b;
	}
	cout << ans * t / c;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
#define showall(obj) for(auto x:obj)cout<<x<<endl;
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
typedef vector<int> vint;
typedef vector<ll> vll;
const int inf = 100100100;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
	int a[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
	int k; cin>>k;
	cout<<a[k-1]<<endl; return 0;
}


Measured memory_bytes: 256
#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 < typename T > string tost( const T& n ) { ostringstream stm; stm << n; return stm.str();}
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);

int N; cin >> N;
vi L(N);
rep(i,N) cin >> L[i];
sort(all(L));
int ans = 0;
for(int i = 0; i < N-2; ++i) {
    for(int j = i+1; j < N-1; ++j) {
        int key = L[i]+L[j];
        int l = j;
        int r = SZ(L);
        while(r - l > 1) {
            int mid = (l + r)/2;
            if(key > L[mid]) l = mid;
            else r = mid;
        }
        ans += l - j;
    }
}
cout << ans << endl;
return 0;
}

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

int main()
{
    int N;
    string S;
    cin >> N >> S;
    int ans = 1;
    if (S.size() == 1)
    {
        cout << 1 << endl;
        return 0;
    }
    rep(i, N - 1)
    {
        if (S.at(i) != S.at(i + 1))
        {
            ans++;
        }
    }
    cout << ans << endl;
}

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

const long long INF = LLONG_MAX;

long long dp[101][100001];

int main()
{
	int n, W;
	cin >> n >> W;
	
	vector < long long > w(n + 1), u(n + 1);
	
	for(int i = 1; i <= n; i++)
	{
		cin >> w[i] >> u[i];
	}
	
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= W; j++)
		{
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			
			if(j >= w[i])
				dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + u[i]);
		}
	}
	
	cout << dp[n][W];
	
	return 0;
}

Measured memory_bytes: 78336
MOD = 998244353
N, K = map(int, input().split())
L = []
R = []
for k in range(K):
    l, r = map(int, input().split())
    L += [l]
    R += [r]
# memo = [[0 for i in range(N+2)] for k in range(K)]
memo = [0 for i in range(N+2)]
memo[1] = 1
memo[2] = -1
cusum = 0
for i in range(1, N+1):
    cusum = (cusum + memo[i]) % MOD
    # print(cusum)
    for k in range(K):
        l, r = L[k], R[k]
        # for j in range(i+l, min(i+r+1, N+1)):
        #     memo[j] += memo[i]
        memo[min(i+l, N+1)] += cusum
        memo[min(i+r+1, N+1)] -= cusum
    # print(memo)
# for i in range(1, N+1):
#     for k in range(K):
#         memo[k][i+1] += memo[k][i]
print(cusum % MOD)

Measured memory_bytes: 81352
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
d=0
for i in range(n-1):
    if a[i+1]-a[i]==1:
        d+=c[a[i]-1]
print(sum(b)+d)

Measured memory_bytes: 3064
/*
  Author: @yash_31
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional>
#define ll long long int
#define eb emplace_back
#define fatafat ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD 1000000007
#define ft first
#define sd second
#define mkpr make_pair
#define deb(x) std::cout<<#x<<":"<<x<<endl;
#define whole(x) (x).begin(),(x).end()
#define revwhole(x) (x).rbegin(),(x).rend()
#define endl "\n"
#define fbo find_by_order
#define ook order_of_key
#define init0(x) memset(x,0,sizeof(x));

using namespace std; 
using namespace __gnu_pbds;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update> gharKaSet;
 
const int maxlimit=2e5+2;
const ll inf=1e18;
//TTBDC

int main()
{
  fatafat
  int n;
  ll wt;
  cin>>n>>wt;
  vector<pair<ll,ll>> arr(n+1);
  int sumval = 0;
  for(int i=1;i<=n;i++){
    cin>>arr[i].ft>>arr[i].sd;
    sumval+=arr[i].sd;
  }
  ll dp[sumval+1];
  for(int i=0;i<=sumval;i++)dp[i]=inf;
  dp[0]=0;
  for(int i=1;i<=n;i++){
    for(int j=sumval;j>=arr[i].sd;j--){
      dp[j]=min(dp[j],dp[j-arr[i].sd]+arr[i].ft);
    }
  }
  for(int i=sumval;i>=0;i--){
    if(dp[i]<=wt){cout<<i;return 0;}
  }
  return 0;
}

Measured memory_bytes: 4364
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
const int mod =1000000007;
const int INF = 1e18;
#define rep(i,a,n) for(int i=a;i<n;i++)
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    if(c-a==1){cout<<1;}
    else{cout<<0;}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using LL  = long long;
using VI  = vector<LL>;
using VVI = vector<VI>;
using VB  = vector<bool>;
using VS  = vector<string>;
using PII = pair<LL, LL>;
using VP  = vector<PII>;
#define PB           push_back
#define MP           make_pair
#define SZ(a)        LL((a).size())
#define EACH(x, c)   for (auto x : (c))
#define ALL(c)       (c).begin(), (c).end()
#define REVERSE(c)   reverse(ALL(c))
#define SORT(c)      stable_sort(ALL(c))
#define RSORT(c)     stable_sort((c).rbegin(), (c).rend())
#define FSORT(c)     stable_sort(ALL(c), [] (auto& x, auto& y) {return x.first < y.first;});
#define FRSORT(c)    stable_sort(ALL(c), [] (auto& x, auto& y) {return x.first > y.first;});
#define SSORT(c)     stable_sort(ALL(c), [] (auto& x, auto& y) {return x.second < y.second;});
#define SRSORT(c)    stable_sort(ALL(c), [] (auto& x, auto& y) {return x.second > y.second;});
#define FOR(i, a, b) for (LL i = (a); i < (b); ++i)
#define REP(i, n)    FOR(i, 0, n)
#define DEBUG true
#define $(x) {if (DEBUG) {cout << #x << " = " << (x) << endl;}}


int main() {
    LL H, W;
    cin >> H >> W;
    VVI c(10, VI(10));
    VVI A(H, VI(W));
    REP(i, 10) {
        REP(j, 10) {
            cin >> c[i][j];
        }
    }
    REP(i, H) {
        REP(j, W) {
            cin >> A[i][j];
        }
    }
    REP(k, 10) {
        REP(i, 10) {
            REP(j, 10) {
                if (c[i][j] > c[i][k] + c[k][j]) c[i][j] = c[i][k] + c[k][j];
            }
        }
    }
    LL ans = 0;
    REP(i, H) {
        REP(j, W) {
            if (A[i][j] != -1) {
                ans += c[A[i][j]][1];
            }
        }
    }
    cout << ans << endl;
	
    return 0;
}


Measured memory_bytes: 512
S = input()
while len(S) > 0:
    if ''.join(S[-5:]) == 'dream' or ''.join(S[-5:]) == 'erase':
        S = S[:-5]
    elif ''.join(S[-6:]) == 'eraser':
        S = S[:-6]
    elif ''.join(S[-7:]) == 'dreamer':
        S = S[:-7]
    else:
        print('NO')
        quit()
print('YES')

Measured memory_bytes: 134968
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#include <utility>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const double EPS = 1e-9;


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

  int n, i;
  cin >>n>>i;
  cout << n - i + 1 << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
const int INF = 100100100;
const double PI = 3.14159265358979323846;
typedef long long ll;
#define FOR(i, a, b) for (ll i = (a); i < (b); ++i)
#define REP(i, n) for (ll i = 0; i < (n); ++i)

int main() {
  ll n, ans = 0;
  cin >> n;
  for (ll i = 1; i <= n; i += 2) {
    ll count = 0;
    for (ll j = 1; j <= i; j += 2) {
      if (i % j == 0) count++;
    }
    // if (i % (ll)sqrt(i) == 0) count++;
    if (count == 8) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
s = input()
n = int(s)

questions = []
copy = []
answer = 0

x = input().split()

for num in range(len(x)):
    questions.append(x[num])
    copy.append(x[num])

v = input()
m = int(v)

for num in range(m):
    d = input().split()
    questions[int(d[0]) - 1] = int(d[1])
    for y in range(len(questions)):
        answer += int(questions[y])
    print(answer)
    answer = 0
    for z in range(len(questions)):
        questions[z] = copy[z]
    





    


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

int main(){
    int n;
    cin >> n;
    int cnt = 0;
    rep(i, n){
        int num = i+1;
        if(num%2 == 0) continue;
        int div_cnt = 0;
        rep(j, num){
            int divider = j+1;
            if(num%divider == 0) div_cnt++;
        }
        if(div_cnt == 8) ++cnt;
    }
    cout << cnt << endl;
}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
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; }
typedef long long ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;

ll dp[101][5][2];

int main()
{
    string N;
    int K;

    cin >> N >> K;

    dp[0][0][0] = 1;

    int len = (int)N.size();
    rep(i, len) {
        rep(j, 4) {
            rep(k, 2) {
                int D = N[i] - '0';
                for (int d = 0; d <= (k ? 9 : D); d++) {
                    dp[i + 1][j + (d != 0 ? 1 : 0)][k || (d < D)] += dp[i][j][k];
                }
            }
        }
    }

    cout << dp[len][K][1] + dp[len][K][0] << endl;


    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int vis[55];
int p[55][55];

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

    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>> a >> b;
        vis[a]++;
        vis[b]++;
        p[a][b]++;
        p[b][a]++;
    }
    int sum=0;
    int f=1;
    while(f)
    {
        f=0;
        int xi=-1;
        for(int i=1; i<=n; i++)
        {
            if(vis[i] == 1)
            {
                f=1;
                sum++;
                xi=i;
                vis[i]--;
                break;
            }
        }
        if(!f)break;

        for(int i=1; i<=n; i++)
        {
            if(p[xi][i])
            {
                vis[i]--;
                p[xi][i]--;
            }
        }
    }
    cout << sum <<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
#include<algorithm>
#include<functional>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll, int> plli;
typedef pair<int, pii> pipii;
typedef vector<vector<int> > mati;
typedef vector<vector<double> > matd;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;

#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define REP(i,y) FOR(i, 0, y)

template <typename T>
void vec_print(vector<T> VEC){
  REP(i, VEC.size()){
    cout << VEC[i] << " ";
  }
  cout << "\n";
};

template <typename T>
void mat_print(vector<vector<T> > MAT){
  REP(i, MAT.size()){
    REP(j, MAT[i].size()){
      cout << MAT[i][j] << " ";
    }
    cout << "\n";
  }
};

template <typename CLASS1, typename CLASS2>
class HOGE{
  public:
    CLASS1 key;
    CLASS2 value;
    HOGE(void){
      return;
    };
    HOGE(CLASS1 key, CLASS2 value){
      this->key = key;
      this->value = value;
    };
    ~HOGE(void){
      return;
    };

    void print(void){
      cout << "key : " << key << ", value : " << value << "\n";
      return;
    };
    
    bool operator==(const HOGE &obj){
      return (this->value == obj.value);
    };
    bool operator<(const HOGE &obj){
      return (this->value < obj.value);
    };
    bool operator>(const HOGE &obj){
      return (this->value > obj.value);
    };
};

constexpr int INF = (1<<30);
constexpr ll INFLL = 1LL<<62;
constexpr long double EPS = 1e-12;

int main(){
  cin.tie(0); // cut the cin and cout (default, std::flush is performed after std::cin)
  ios::sync_with_stdio(false); // cut the iostream and stdio (DON'T endl; BUT "\n";)

  ll N;
  cin >> N;
  ll T, A;
  cin >> T >> A;
  vector<HOGE<ll, double>> dp(N);
  REP(i, N){
    ll H;
    cin >> H;
    double Temperature = (double)T-(double)H*0.006;
    HOGE<ll, double> tmp(i, abs(Temperature-A));
    dp[i] = tmp;
  }

  sort(dp.begin(), dp.end());

  cout << dp[0].key+1 << "\n";

  return 0;
}


Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<utility>
#include<queue>
#include<cmath>
#include<cstdio>
using namespace std;
#define REP(i, a,b) for(i=a;i<b;i++) 
#define REP1(i,b,a) for(i=b-1;i>=a;i--)
#define output(x) cout<<x<<endl;
#define pb(x) push_back(x);
typedef long long int ll;
typedef pair<ll, ll > P;
const int MOD = 1000000007;


int main() {
	ll i, j, k, l, m, n, sum, flag, cc, M, X, H, W, N,Y,Z,K;
	cc = 0;
	flag = 0;
	cin >> N>>M;
	vector<ll>x(N);
	vector<ll>y(M);
	REP(i, 0, N) {
		cin >> x[i];
	}
	REP(j, 0, M) {
		cin >> y[j];
	}
	vector<ll>sumx(N);
	vector<ll>sumy(M);
	REP(i, 0, N) {
		sumx[i] = 0;
	}
	REP(i, 0, M) {
		sumy[i] = 0;
	}
	ll sumsumx = 0;
	ll sumsumy = 0;
	REP(i, 0, N-1) {
		sumx[i + 1] = sumx[i] + (x[i + 1] - x[i])*(i + 1);
		sumx[i+1] %= MOD;
		sumsumx += sumx[i + 1];
		sumsumx %= MOD;
	}
	REP(i, 0, M-1) {
		sumy[i + 1] = sumy[i] + (y[i + 1] - y[i])*(i + 1);
		sumy[i + 1] %= MOD;
		sumsumy += sumy[i + 1];
		sumsumy %= MOD;
	}
	output((sumsumx*sumsumy) % MOD);

	return 0;
}





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

#define REP(i,n) for(int i=0;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<29
#define LINF LLONG_MAX/3
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(v) (v).begin(),(v).end()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
#define CININIT cin.tie(0),ios::sync_with_stdio(false)
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

constexpr ll mod = 1e9+7;

int main(){
    string s;
    cin>>s;
    int n = s.size();
    int point=0;
    int p=0,g=0;    // a: p   g : g
    for(int i=0;i<n;i++){
        char c = s[i];
        if(c=='g'){
            if(p<g){
                p++;
                point++;
                cerr<< "p";
            }else{
                g++;
                cerr << "g";
            }
        }else{
            if(p<g){
                p++;
                cerr<< "p";
            }
            else{
                g++;
                point--;
                cerr << "g";
            }
        }
    }
    cerr << endl;
    cout << point << endl;
}


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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl

typedef long long ll;

using namespace std;

const int INF = 1e9,MOD = 1e9 + 7,ohara = 1e6;
const ll LINF = 1e18;
long long int n,cnt=0,ans=0,a,b,c,d,cmp,cmpp,m,h,w,x,y,sum=0,pos,grid[301][301];
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

int main(void){
  
       cin.tie(0);
    ios::sync_with_stdio(false);
      
      cin >> n;
      rep(i,n)rep(j,n)cin>>grid[i][j];
      ll flo[301][301];
      rep(i,n){
          rep(j,n){
              if(i==j)flo[i][j]=0;
              else flo[i][j]=LINF;
          }
      }
      rep(i,n){
          rep(j,n){
              if(i>j)continue;
              flo[i][j]=grid[i][j];
              flo[j][i]=grid[i][j];
          }
      }
      rep(i,n){
          rep(j,n){
              rep(k,n){
                  flo[j][k]=min(flo[j][k],flo[j][i]+flo[i][k]);
              }
          }
      }
      rep(i,n){
          rep(j,n){
              if(i<j)continue;
              if(flo[i][j]!=grid[i][j])fl=true;
          }
      }
      if(fl)Cout(-1);
      else{
      rep(i,n){
          rep(j,n){
              rep(k,n){
if(i==j or i==k)continue;
                  if(flo[j][k]==flo[j][i]+flo[i][k])grid[j][k]=0;
              }
          }
      }
rep(i,n){
rrep(j,i+1,n){
ans+=grid[i][j];
}
}
          Cout(ans);
      }
       
return 0;
}


Measured memory_bytes: 1664
# coding: utf-8
class Case01

  def initialize
  end

  def show
    p self.instance_variables
        .map{ |sym| [sym, self.instance_variable_get(sym)] }
        .to_h
  end
  
  # 実行する
  def execute
    read
    solve
    output
  end

  def read
    @h, @a = gets.chomp.split.map(&:to_i)
  end

  def solve
    if (@h % @a == 0) then
      @result = @h / @a
    else
      @result = @h / @a + 1
    end
  end
  
  def output
    puts @result
  end

end

Case01.new.execute if $0 == __FILE__


Measured memory_bytes: 1788
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

#define MOD 1000000007

int main() {
  ll n;
  cin >> n;
  map<ll, ll> mp;
  for (ll i = 2; i * i <= n; ++i) {
    while (n % i == 0) {
      mp[i]++;
      n /= i;
    }
  }
  if (n != 1) mp[n]++;
  ll ans = 0;
  for (auto a : mp) {
    ll c = a.second;
    ll res = 0;
    for (int i = 1; i <= 50; ++i) {
      if (i <= c) {
        res++;
        c -= i;
      }
    }
    ans += res;
  }
  cout << ans << endl;
  return 0;
}

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

using namespace std;
int arr[100001];
long long ans;
int main()
{
    int n, m;
    priority_queue<int> pq;
    scanf("%d %d",&n,&m);
    for (int i=0;i<n;i++) {
        scanf("%d",&arr[i]);
        pq.push(arr[i]);
    }
    for (int i=0;i<m;i++) {
        int t=pq.top();
        pq.pop();
        t/=2;
        pq.push(t);
    }
    for (int i=0;i<n;i++) {
        int t=pq.top();
        ans += t;
        pq.pop();
    }
    printf("%lld",ans);
}


Measured memory_bytes: 1148
def divisor(n)
  res = []
  (1..Math.sqrt(n)).each do |i|
    if (n % i).zero?
      res << i
      res << n/i
    end
  end
  res.sort
end
N = gets.to_i
m = 1
ans = 0
while m <= N
  d = divisor m
  ans += 1 if d.length == 8
  m += 2
end
puts ans

Measured memory_bytes: 14320
#include<stdio.h>
int main(void){
    int a,b;
    scanf("%d",&a);
    scanf("%d",&b);
    if(a==b) {
        printf("a == b\n");
    }
    if(a>b) {
        printf("a > b\n");
        
    }
    if(a<b) {
        printf("a < b\n");
    }
    return 0;
}


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

int main() {
  string s;
  cin >> s;
  if (s.at(5) == '0' && s.at(6) > 52) {
    cout << "TBD" << endl;
  } else if (s.at(5) == '1') {
    cout << "TBD" << endl;
  } else if (s.at(5) == '0' && s.at(6) <= 52) {
    cout << "Heisei" << endl;
  }
}
  

Measured memory_bytes: 256
#include <iostream>
#include<cstring>
using namespace std;
int f(char *a,int m,int n)
{
    m--;
    n--;
    while(m<n)
    {
        if(a[m]!=a[n])
            return 0;
        m++;
        n--;
    }
    return 1;
}
int main()
{
    int m,n;
    char a[10000];
    cin>>a;
    n=strlen(a);
    int flag=f(a,1,n)*f(a,1,(n-1)/2)*f(a,(n+3)/2,n);
    if(flag)
        cout<< "Yes";
    else cout<< "No";
    return 0;
}


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

int main() {
	int n;
	cin >> n;
	vector<vector<vector<int>>>xy(n, vector<vector<int>>(0, vector<int>(2)));
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		for (int j = 0; j < a; j++) {
			int x, y;
			cin >> x >> y, x--;
			xy.at(i).push_back({ x,y });
		}
	}
	int ans = 0;
	for (int bit = 0; bit < (1 << n); bit++) {
		vector<int> l(0);
		vector<int> hu(n, -1);
		for (int i = 0; i < n; i++) {
			if (bit & (1 << i)) {
				l.push_back(i);
				hu.at(i) = 1;
			}
			else hu.at(i) = 0;
		}
		bool b = false;
		for (int i = 0; i < l.size(); i++) {
			for (int j = 0; j < xy.at(l.at(i)).size(); j++) {
				int x = xy.at(l.at(i)).at(j).at(0);
				int y = xy.at(l.at(i)).at(j).at(1);
				if (hu.at(x) == y)continue;
				else {
					b = true;
					break;
				}
			}
			if (b)break;
		}
		if (b)continue;
		else ans = max(ans, (int)l.size());
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int b,f,r,v;
int i,s,t;
int n;
int x;


int hoge[4][3][10];

main(){
	scanf("%d",&n);
	for(i=0; i<n; i++){
		scanf("%d %d %d %d",&b,&f,&r,&v);
		switch(b){
			case 1:hoge[1][f][r]+=v;
			break;
			
			case 2:hoge[2][f][r]+=v;
			break;
			
			case 3:hoge[3][f][r]+=v;
			break;
			
			case 4:hoge[4][f][r]+=v;
			break;
		}
	}
	
	for(i=1; i<=4; i++){
		for(s=1;s<=3;s++){
			for(t=1;t<=10;t++){
				printf(" %d",hoge[i] [s] [t]);
				
			}
			printf("\n");
		}
		if(i!=4){printf("####################\n");}
	}
	return 0;
}

Measured memory_bytes: 612
#include <bits/stdc++.h>
#define rep(i,n) for(long long int i = 0; i < n; i++)
#define print(n) std::cout << n << std::endl
#define _print(n) std::cout << n
using namespace std;
typedef long long ll;
const int N = 1000000;

int main(){
    int n; cin >> n; print((1+n)*n/2);
}

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

using ll = long long;

using namespace std;

int main() {
    int h, w, a, b;
    cin >> h >> w >> a >> b;
    for (int i=0; i<h; i++) {
        for (int j=0; j<w; j++)
            cout << ((i < b) xor (j < a));
        cout << '\n';
    }
    return 0;
}

Measured memory_bytes: 1280
#include<cstdio>
#include<iostream>
#define M 50

int main(void)
{
	int n,r;
	int p,c;
	int i,j,k,l;
	int a[M],temp[M];
	
	for(;;)
	{
		scanf("%d %d",&n,&r);
		if(n==0 && r==0) break;
		
		for(i=0; i<n; i++)
		{
			a[i]=i+1;
			temp[i]=i+1;
		}
		
		for(j=0; j<r; j++)
		{
			scanf("%d %d", &p, &c);
			
			for(i=0; i<n; i++)
			{
				temp[i]=a[i];
			}
			
			for(k=n-p; k<n; k++)
			{
				a[k-c+1]=a[k+1]; //落ちてくる部分の配列
			}

			for(k=0; k<c; k++)
			{
				a[n-c+k]=temp[n-p-c+1+k]; //上に上がる部分の配列
			}

		}
		printf("%d\n",a[n-1]);
	}
	
	
	return 0;
}

Measured memory_bytes: 1188
#include <stdio.h>

int main(){
int a,b,c,d;
while(scanf("%d %d",&a,&b) != EOF){
d=10;
for(c=1;c<=16;c++){
if(d>(a+b)) break;
d=d*10;
}
printf("%d\n",c);
}
return 0;
}

Measured memory_bytes: 0