akhauriyash/Code-Regression huggingface dataset:
s = input()
t = input()

ret = -1


t_len = len(t)


for i in range(len(s)-t_len+1):
    cut_seq = s[i:i+t_len]
    for j in range(t_len):
        if cut_seq[j] != t[j] and cut_seq[j] != '?':
            break
    else:
        ret = max(ret, i)


if ret == -1:
    print('UNRESTORABLE')
else:
    print((s[:ret] + t + s[ret + t_len:]).replace('?', 'a'))

Measured memory_bytes: 38256
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
#include<fstream>
#include<set>
using namespace std;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define out(str) cout << str << endl
#define ALL(a) (a).begin(),(a).end()
#define INF (1<<29)

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 (b<a) { a=b; return 1; } return 0; }

int a;
string s;

int main(){
    cin>>a>>s;
    if(a>=3200)out(s);
    else out("red");
    
    
}


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

#pragma GCC optimize("O3,Ofast,no-stack-protector,unroll-loops,fast-math")

#define int long long
typedef pair <int, int> pii;

const int inf = 2e18;

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int h, n;
	cin >> h >> n;
	int a[n], b[n];
	for (int i = 0; i < n; i++)
		cin >> a[i] >> b[i];
	int dp[h + 1];
	fill(dp, dp + h + 1, inf);
	dp[0] = 0;
	for (int i = 1; i <= h; i++) {
		for (int j = 0; j < n; j++) {
			if (a[j] > i) {
				dp[i] = min(dp[i], b[j]);
			}
			else {
				dp[i] = min(dp[i], dp[i - a[j]] + b[j]);
			}
		}
	}
	cout << dp[h];
}



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

template<typename T_char>
T_char ToUpper(T_char cX){return toupper(cX);}

int main(){
  int n; cin >> n;
  vector<string> s(n);
  for(int i=0; i<n; ++i) cin >> s[i];

  int c = 0;
  int c1 = 0;
  int c2 = 0;
  int c3 = 0;
  for(int i=0; i<n; ++i){
    if(s[i]=="AC") c++;
    else if(s[i]=="WA") c1++;
    else if(s[i]=="TLE") c2++;
    else if(s[i]=="RE") c3++;
  }

  cout << "AC" << " " << 'x' << " " << c <<endl;
  cout << "WA" << " " << 'x' << " " << c1 <<endl;
  cout << "TLE" << " " << 'x' << " " << c2 <<endl;
  cout << "RE" << " " << 'x' << " " << c3 <<endl;
}

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

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

    int n;
    cin >> n;

    bool ans = false;
    REP(i, 26) REP(j, 15) {
        if (i * 4 + j * 7 == n) {
            ans = true;
            break ;
        }
    }

    if (ans) cout << "Yes" << '\n';
    else cout << "No" << '\n';
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define rrep2(ri,x,n) for(int ri = (int)(n-1); ri >= (int)(x); ri--)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

int main(){
  string s;
  cin >> s;
  string nx;
  rep(i, s.size()){
    if(s.at(i) != 'x') nx.push_back(s.at(i));
  }
  string rnx = nx;
  reverse(rnx.begin(), rnx.end());
  if(rnx != nx){
    cout << -1 << endl;
    return 0;
  }
  vector<int> xx(nx.size()+1, 0);
  int index = 0;
  rep(i, nx.size()){
    if(s.at(index) ==  'x'){
      xx.at(i)++;
      i--;
    }
    index++;
  }
  xx.back() = s.size() - (index);
  // for(int i : xx){
  //   cerr << i << " ";
  // }
  // cerr << endl;
  int ans = 0;
  rep(i, xx.size()/2){
    ans += abs(xx.at(i)-xx.at(xx.size()-i-1));
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3988
import java.util.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Map;
import java.util.TreeMap;
import java.util.HashMap;

class Main{
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
 
        int X = sc.nextInt();
        for(int i=-1000; i<=1000; i++){
            for(int j=-1000; j<=1000; j++){
                double Y = Math.pow(i, 5) - Math.pow(j, 5);
                if(Y==X){
                    System.out.println(i + " " + j);
                    return;
                }
            }
        }
    }
}

Measured memory_bytes: 38844
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    string S;
    cin >> S;

    int y = stoi(S.substr(0, 3));
    int m = stoi(S.substr(5, 6));
    int d = stoi(S.substr(8, 9));

    if (y = 2019) {
       if (m <= 4) {
           cout << "Heisei" << endl;
       } else {
           cout << "TBD" << endl;
       }
    } else if (y < 2019) {
        cout << "Heisei" << endl;
    } else {
        cout << "TBD" << endl;
    }
}

Measured memory_bytes: 256
import java.util.Scanner;

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

	int n = scan.nextInt();
	int[] v = new int[n];
	int[] c = new int[n];

	for(int i = 0; i < n; i++){
	    v[i] = scan.nextInt();
	}
	for(int i = 0; i < n; i++){
	    c[i] = scan.nextInt();
	}

	int value = 0;
	for(int i = 0; i < n; i++){
	    if(v[i] - c[i] > 0){
		value += (v[i]-c[i]);
	    }
	}

	System.out.println(value);
    }
}
	    
       


Measured memory_bytes: 25172
a, b, c, d = map(int, input().split())

A = [a, b]
C = [c, d]

if a * b <= 0 or c * d <= 0:
    C.append(0)
kouho = []
for x in A:
    for y in C:
        kouho.append(x * y)
print(max(kouho))


Measured memory_bytes: 61684
import collections as c
ip = lambda : map(int, input().split())
# ##############
N = int(input())
l = [[],[]]
for i in range(N):
    s,t = input().split()
    l[0].append(s)
    l[1].append(int(t))
X = input()
ix = l[0].index(X)
# print(ix)
print(sum(l[1][ix+1:]))

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

int main(){
    int n,a;
    cin >> n;
    int k = n;
    int twos=0,fours=0;
    while(n--){
		cin >> a;
		if(a%4==0) fours++;
		else if (a%2==0) twos++;
	}
	int rest = max(k-(fours*2+1),0);
	//cout << rest << endl;
	if(rest == 0) cout << "Yes";
	else if ((rest+1)>twos) cout << "No";
	else cout << "Yes";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<ll,ll>;
using PP=pair<ll,P>;
using vp=vector<P>;
using vpp=vector<PP>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
int main(){
    ll a,b,c;
    cin>>a>>b>>c;
    cout<<b+min(c,a+b+1)<<endl;
    return 0;
}

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

int a[200001]={};
int b[200001]={};

int main(){
  long N;
  cin >> N;
  for(long i=1; i<=N; i++){
    cin >> a[i];
  }
  long M=0;
  if(a[N]==1){
    M++;
    b[N]=1;
  }
  for(long i=N-1; i>=1; i--){
    long c=0;
    for(long j=i; j<=N; j+=i){
      if(b[j]==1) c++;
    }
    if(c%2!=a[i]){
      b[i]=1;
      M++;
    }
  }
  cout << M << endl;
  if(M!=0){
    for(long i=1; i<=N; i++){
      if(b[i]==1) cout << i << " ";
    }
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 2432
#include<bits/stdc++.h>
using namespace std;
///Welcome to Nasif's Code
#define bug printf("bug\n");
#define bug2(var) cout<<#var<<" "<<var<<endl;
#define co(q) cout<<q<<endl;
#define all(q) (q).begin(),(q).end()
typedef long long int ll;
typedef unsigned long long int ull;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
#define pi acos(-1)
#define inf 1000000000000000LL
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main()
{
    FastRead
    //freopen("output.txt", "w", stdout);
   int a,b;
   cin>>a>>b;
   a--;
   b--;
   cout<<a*b<<endl;

    return 0;
}


Measured memory_bytes: 3504
n,w_limit = map(int,input().split())
w_ls = [0] * n
v_ls = [0] * n
for i in range(n):
    w_ls[i],v_ls[i] = map(int,input().split())
dp = [[0] * (w_limit+1) for _ in range(n+1)]
for i in range(1,n+1):
    for w in range(w_limit+1):
        if w - w_ls[i-1] >= 0:
            dp[i][w] = dp[i-1][w-w_ls[i-1]] + v_ls[i-1]
        dp[i][w] = max(dp[i][w], dp[i-1][w])
print(dp[-1][w_limit])


Measured memory_bytes: 149128
#include<iostream>
#include<cmath>

int main(void)
{
  int N;
  std::cin >> N;
  int X[N];
  double sum=0;
  for(int i=0;i<N;i++)
  {
    std::cin >> X[i];
    sum = sum + X[i];
  }

  double P = sum/N;

  int P1 = std::floor(P);
  int P2 = std::ceil(P);
  
  int sum1=0;
  int sum2=0;
  for(int i=0;i<N;i++)
  {
    sum1 = sum1 + (X[i]-P1)*(X[i]-P1);
    sum2 = sum2 + (X[i]-P2)*(X[i]-P2);
  }
  
  if(sum1<sum2)
  {
    std::cout << sum1;
  }else
  {
    std::cout << sum2;
  }
    
  return 0;
}

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

int main()
{
	int n,i,j,maxv=0,sum=0,minv=999999999;
	cin>>n;
	int a[n+1];
	
	for(i=1;i<=n;i++){
	   cin>>a[i];
	   if(a[i]>maxv)
	     maxv=a[i];
	}
	   
	int u=0; 
	for(i=1;i<=maxv;i++)
	{
		sum=0;
		for(j=1;j<=n;j++){
		   u=abs(a[j]-i);
		   sum+=u*u;
		}
		if(sum<minv)
		  minv=sum; 
	}
	
	cout<<minv;
	
	return 0;
	
}

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

int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    sort(A.begin(), A.end());
    A.erase(unique(A.begin(), A.end()), A.end());
    int n = (int)A.size();
    cout << n - (1 - n % 2) << endl;
    return 0;
}


Measured memory_bytes: 640
#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 a, b;
    cin >> a >> b;
    int ans = 6 - (a + b);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3612
#include<cstdio>
using namespace std;
int main()
{
	int a,b;
	scanf("%d %d",&a,&b);
	if(a==b)	printf("Draw");
	if(a ==1 && b != 1)	printf("Alice");	
	if(b ==1 && a != 1)	printf("Bob");	
	if(a > b&&b != 1)	printf("Alice");
	if(a < b&&a != 1)	printf("Bob");
	return 0;
}

Measured memory_bytes: 128
# -*- coding: utf-8 -*-
N = int(input())
A = sorted(list(map(int, input().split())), reverse=True) # 降順にソート
count = 0
score = 0
i = 0
while count < N-1:
  if i == 0:
    score += A[0]
    count += 1
    i += 1
    continue
  score += A[i]
  count += 1
  if count < N-1:
    score += A[i]
    count += 1
  i += 1
print(score)

Measured memory_bytes: 104956
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=i
 if l<H and A[g]<A[l]:g=l
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))


Measured memory_bytes: 64176
#include <stdio.h>
#include <iostream>
using namespace std;
 
int main()
{
  int a, b;
  cin >> a >> b;
  int ans = 1;
  int za = 0;
  int n;
  while (scanf("%d", &n) != EOF) {
    za += n;
    if(za <= b) ans++;
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define show(x) for(auto i: x){cout << i << " ";}
#define showm(m) for(auto i: m){cout << m.x << " ";}
typedef long long ll;
typedef pair<int, int> P;


int main()
{
    ll h;
    cin >> h;

    int ans_sub = 0;
    while(h != 1){
        h >>= 1;
        ans_sub++;
    }

    ll ans = 1ll<<(ans_sub+1);
    ans -= 1;
    cout << ans << endl;
}



Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

namespace Poll
{
    class Program
    {
        static void Main(string[] args)
        {
            var nInput = int.Parse(Console.ReadLine());            
            var inputs = new Dictionary<string, int>();
            for (int i = 0; i < nInput; i++)
            {
                var input = Console.ReadLine();

                if (!inputs.ContainsKey(input))
                {
                    inputs[input] = 1;
                }
                else
                {
                    inputs[input]++;
                }
            }
            var maxValue = inputs.Values.Select(x => x).Max();                         
            List<KeyValuePair<string, int>> sortedList = inputs.Where(x => x.Value == maxValue).ToList();
            List<string> outputList = new List<string>();           

            for(int i = 0; i< sortedList.Count(); i++)
            {
                outputList.Add(sortedList[i].Key);
            }

            outputList.Sort(String.CompareOrdinal);

            foreach(string item in outputList)
            {
                Console.WriteLine(item);
            }               
        }
    }
}


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

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

    int n, a ,b;

    cin >> n >> a >> b;
    if (n * a > b) {
      cout << b << endl;
    } else {
      cout << n * a << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
using Int = long long;
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n,m) for(int i=n;i<m;i++)
template <typename Container> void P(const Container &c) {
    for (const auto& x : c) cout << x << ' '; cout << '\n';
}
const int MOD = 1000000007;
int main()
{
    int a, b, c; cin >> a >> b >> c;
    cout << min({a+b, b+c, c+a}) << endl;
    return 0;
}


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

#define int long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define dbg(x) cerr << #x << ": " << x << endl;
#define dbg2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define dbg3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define dbgB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl;
#define line() cerr << "---------------" << endl;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const double PI = 3.14159265358979323846;

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 (b<a) { a = b; return 1; } return 0; }

template<typename T>
void print1(T begin, T end) {
	while (begin != end) {
		cerr << (*begin) << " ";
		*begin++;
	}
	cerr << endl;
}

template<typename T>
void print2(T Array, int height, int width) {
	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			cerr << " " << Array[i][j];
		}
		cerr << endl;
	}
}

void print() { std::cerr << endl; }
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
	std::cerr << head << " ";
	print(std::forward<Tail>(tail)...);
}

template<class T>
void Add(T &a, const T &b, const T &mod=1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}

template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

// ------------------------------------------------------------------------------------------

const int mod = 1e9 + 7;
int dp[100005][2];

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

	dp[0][0] = 1;
	rep (i, s.size()) {
		{
			// j == 0
			int lim = (s[i] - '0' + 1);
			if (lim == 1) {
				(dp[i+1][0] += dp[i][0]) %= mod;
			} else {
				(dp[i+1][0] += dp[i][0] * 2) %= mod;
				(dp[i+1][1] += dp[i][0]) %= mod;
			}
			{
				// j==1
				int lim = 2;
				(dp[i+1][1] += dp[i][1]) %= mod;
				(dp[i+1][1] += dp[i][1] * 2) %= mod;
			}
		}
	}

	int ans = (dp[s.size()][0] + dp[s.size()][1]) % mod;

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 2048
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    vector<int> a(n*2);
    for (int i = 0; i < n*2; ++i) cin >> a[i];
    sort(a.begin(), a.end());
    int su = 0;
    for (int i = 0; i < n*2; i += 2) su += a[i];
    cout << su;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#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, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

const ll mod = 1e9 + 7;

ll mylcm(ll a, ll b) {
    return a * b / __gcd(a, b);
}

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

    ll n, m;
    cin >> n >> m;
    ll g = 1, mem, tmp;
    vll a(n);
    REP(i, n) {
        cin >> a[i];
        g = mylcm(g, a[i] / 2);
        if (g > m) {
            cout << 0 << endl;
            return 0;
        }
        tmp = 0;
        while (a[i] % 2 == 0) {
            a[i] /= 2;
            tmp++;
        }
        if (i && tmp != mem) {
            cout << 0 << endl;
            return 0;
        }
        mem = tmp;
    }

    ll res = (m - g) / (2 * g) + 1;
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
int gcd(int a, int b)
{
    if(b == 0) return a;
    return gcd(b, a%b);
}
int main()
{
    int x;
    cin >> x;
    int a = gcd(x, 360);
    cout << (x * 360 / a) / x << endl;
}


Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <map>
#include <algorithm>
#include <functional>
#include <string>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>
using namespace std;

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

using ll = long long int;
using pll = pair<ll, ll>;

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

    vector<ll> P(N);
    rep (i, N) { cin >> P[i]; }

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

    ll ans = 0;
    rep (i, K) { ans += P[i]; }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3632
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

X = int(input())
fac = {}
fac[0] = 0
for i in range(1, 50000):
    fac[i] = fac[i-1]+i
    if fac[i]>=10**9:
        break

for i in range(1, 50000):
    f = fac[i]
    if f>=X:
        print(i)
        break

Measured memory_bytes: 71756
/*
 * Author       : YangDavid
 * Created Time : 2019年09月26日 星期四 22时49分26秒
 */

#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int K = 38, N = K * (K - 1) + 1;

int a[N][K];
int getV(int x, int y) { return (K - 1) * (x%(K-1)) + (y%(K-1)) + K + 1; }
void gen() {
    rep(i, K) a[0][i] = i + 1;
    for(int i = 1; i < K; ++i) {
        for(int j = (i-1)*(K-1) + 1, c = 0; j <= i*(K-1); ++j, ++c) {
            a[j][0] = i;
            for(int k = 1; k < K; ++k)
                a[j][k] = getV(c + (k - 1) * (i - 1), k - 1);
        }
    }
    for(int j = (K-1)*(K-1) + 1, c = 0; j <= K*(K-1); ++j, ++c) {
        a[j][0] = K;
        for(int k = 1; k < K; ++k)
            a[j][k] = getV(k - 1, c);
    }
}

int main() {
    gen();
    printf("%d %d\n", N, K);
    rep(i, N) rep(j, K) 
        printf("%d%c", a[i][j], " \n"[j == K - 1]);

    return 0;
}


Measured memory_bytes: 640
#include <iostream>
 #include <string>
 using namespace std;
 int main(){
 string s;
 cin>>s;
 if(s=="Sunny") cout<<"Cloudy"<<endl;
 if(s=="Cloudy") cout<<"Rainy"<<endl;
 if(s=="Rainy") cout<<"Sunny"<<endl;
 return 0;
 }


Measured memory_bytes: 256
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream> 
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
using namespace std;
#define eps 0.000000001
#define LONG_INF 10000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define REP(i,n) for(long long i = 0;i < n;++i)
long long dp[2000][2000] = {};//1???????????????->?????????t??????????????§???????????????2???????????????->?????????s??¨???????????§?????´?????????
int main() {
	string t, b;
	cin >> t >> b;
	dp[0][0] = 1;//t???????????????????????¶?????§???????????¶b??¨?????´?????????????????????????????????
	for (int i = 0;i < t.length();++i) {
		//t[i]?????????????????????
		//???????????§?????????????????£???????????????????????????????????\???????????????
		dp[i + 1][b.length()] += dp[i][b.length()];
		dp[i + 1][b.length()] %= MAX_MOD;
		for (int q = 0;q < b.length();++q) {
			//b[q]??¨t[i]????????´??????????????????
			if (b[q] == t[i]) {
				//t[i]??????????????¨?????????????????¨??§???s[q]??¨?????´???????????§?¬???????????????¢????????????
				dp[i + 1][q + 1] += dp[i][q];
				dp[i + 1][q + 1] %= MAX_MOD;//???????????¨???
			}
			//t[i]?????????????????????????????£?????¨????????????????¶????s[q]??¨?????´?????????????????¢???
			dp[i + 1][q] += dp[i][q];
		}
	}
	//t?????¨????????????????????§????????????b??¨??????????????????????????´????????????????????°?????????
	cout << dp[t.length()][b.length()] << endl;
	return 0;
}


Measured memory_bytes: 14852
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

int n,q,num[100010],sum[100010],ans[100010];
vector<pair<pair<int,int>,int> > g[100010];
vector<pair<pair<int,int>,pair<int,int> > > v[100010];
int par[20][100010];
int dep[100010],dist[100010];

inline void dfs(int u,int pr,int dist)
{
	par[0][u]=pr;
	dep[u]=dist;
	for(int i=0;i<g[u].size();i++){
		if(g[u][i].first.first!=pr) dfs(g[u][i].first.first,u,dist+1);
	}
}
	
inline void init()
{
	dfs(1,-1,0);
	for(int k=0;k+1<20;k++){
		for(int i=1;i<=n;i++){
			if(par[k][i]<0) par[k+1][i]=-1;
			else par[k+1][i]=par[k][par[k][i]];
		}
	}
}
	
inline int lca(int u,int w)
{
	if(dep[u]>dep[w]) swap(u,w);
	for(int k=0;k<20;k++){
		if(((dep[w]-dep[u])>>k)&1){
			w=par[k][w];
		}
	}
	if(u==w) return u;
	for(int k=20-1;k>=0;k--){
		if(par[k][u]!=par[k][w]){
			u=par[k][u];w=par[k][w];
		}
	}
	return par[0][u];
}

inline void dfs2(int x,int pr)
{
	for(int i=0;i<g[x].size();i++){
		int u=g[x][i].first.first;
		if(u==pr) continue;
		dist[u]=dist[x]+g[x][i].first.second;
		dfs2(u,x);
	}
}

inline void dfs3(int x,int pr)
{
	for(int i=0;i<v[x].size();i++){
		int idx=v[x][i].first.first;
		int val=dist[x]-sum[v[x][i].second.first]+num[v[x][i].second.first]*v[x][i].second.second;
		ans[idx]+=val*v[x][i].first.second;
	}
	for(int i=0;i<g[x].size();i++){
		int u=g[x][i].first.first;
		if(u==pr) continue;
		num[g[x][i].second]++;
		sum[g[x][i].second]+=g[x][i].first.second;
		dfs3(u,x);
		num[g[x][i].second]--;
		sum[g[x][i].second]-=g[x][i].first.second;
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin>>n>>q;
	for(int i=1;i<n;i++){
		int x,y,c,d;
		cin>>x>>y>>c>>d;
		g[x].push_back(make_pair(make_pair(y,d),c));
		g[y].push_back(make_pair(make_pair(x,d),c));
	}
	init();
	dfs2(1,-1);
	for(int i=1;i<=q;i++){
		int u,w,x,y;
		cin>>x>>y>>u>>w;
		int p=lca(u,w);
		v[u].push_back(make_pair(make_pair(i,1),make_pair(x,y)));
		v[w].push_back(make_pair(make_pair(i,1),make_pair(x,y)));
		v[p].push_back(make_pair(make_pair(i,-2),make_pair(x,y)));
	}
	dfs3(1,-1);
	for(int i=1;i<=q;i++) cout<<ans[i]<<endl;
	return 0;
}

Measured memory_bytes: 28660
#include<cstdio>
#include<iostream>
#include<string>
#include <functional>
#include<queue>

using namespace std;

int main(void){

	priority_queue<int,vector<int>,greater<int> > data,data2;
	int sum,cnt=0;
	int min=-1,max=-1;
	int sta,w;
	string inp,num("");
	bool f=true;

	while(1){
		inp=getchar();
		if(inp=="\n"){
			f=true;
			inp=getchar();
			if(inp=="\n") break;
		}
		if(inp==","){
			sta=num.length()-1;
			w=1;
			sum=0;
			for(int j=sta;j>=0;j--){
				sum+=w*(num[j]-'0');
				w*=10;
			}
			data.push(sum);
			if(min==-1) min=sum,max=sum;
			else{
				if(min>sum) min=sum;
				if(max<sum) max=sum;
			}
			num=("");
			f=false;
		}
		if(f){
			num+=inp;
		}
	}

	while(cin>>inp){
		num=("");
		for(int j=0;;j++){
			if(inp[j]==','){
				break;
			}
			num+=inp[j];
		}
		sta=num.length()-1;
		w=1;
		sum=0;
		for(int j=sta;j>=0;j--){
			sum+=w*(num[j]-'0');
			w*=10;
		}
		data2.push(sum);
	}

	while(!data.empty()&&!data2.empty()){
		if(data.top()==data2.top()){
			sum=data.top();
			cnt=0;
			while(!data.empty()){
				if(data.top()!=sum) break;
				cnt++;
				data.pop();
			}
			while(!data2.empty()){
				if(data2.top()!=sum) break;
				cnt++;
				data2.pop();
			}
			cout<<sum<<" "<<cnt<<endl;
		}
		else if(data.top()<data2.top()) data.pop();
		else data2.pop();
	}

	return 0;
}

Measured memory_bytes: 1212
#include <algorithm>
#include <numeric>
#include <map>
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

#define REP(i,n) for(int i=0;i<n;i++)
#define ALL(a) a.begin(),a.end()
#define EACH(it,a) for(auto it=a.begin();it!=a.end();it++)

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


int INF=1<<28;

namespace ShortestPath{
    struct Edge{
        int from,to,cost;
        Edge(int from,int to,int cost)
            : from(from),to(to),cost(cost) {};
    };
    ostream& operator <<(ostream& os,const Edge& e){
            os<<"("<<e.from<<"->"<<e.to<<")";
            return os;
    }
    struct Task{
        int prev,pos,cost;
        Task(int prev,int pos,int cost)
            :prev(prev),pos(pos),cost(cost){};
        bool operator>(const Task& r) const{
            return cost>r.cost;
        }
    };
    typedef vector<vector<Edge> > Graph;
    typedef  vector<vector<int> > Mat;

    //verified by codoforces 144D http://codeforces.com/contest/144/submission/4976825
    // // 負の辺がない
    // // O(E*logV)
    vector<int> dijkstra(const Graph& g,const int s,vector<int>& prev){
        const int V=g.size();
        vector<int> d(V,INF);d[s]=0;
        fill(ALL(prev), -2);
        priority_queue<Task,vector<Task>,greater<Task> > que;
        que.push(Task(-1,s,0));
        while(!que.empty()){
            Task task=que.top();que.pop();
            //if(prev[task.pos]!=-2)continue;
            if(d[task.pos]<task.cost)continue;
            prev[task.pos]=task.prev;
            EACH(e,g[task.pos]){
                if(d[e->to]>d[e->from]+e->cost){
                    d[e->to]=d[e->from]+e->cost;
                    que.push(Task(e->from,e->to,d[e->to]));
                }
            }   
        }
        return d;
    }
    vector<int> dijkstra(const Graph& g,const int s){
        vector<int> prev(g.size());return dijkstra(g,s,prev);
    }
}
using namespace ShortestPath;


int W,H;
int enc(int y,int x){
	return y*W+x;
}


int main() {


	while (true) {
		cin >> W >> H;if(W==0 && H==0)break;
        

        Graph g(W*H);
        
		REP(inpy,2*H-1){
			int y=inpy/2;
			if(inpy%2==0){
				REP(x,W-1){
					int b;cin >> b;
					if(b==0){
						g[enc(y,x)].push_back(Edge(enc(y,x),enc(y,x+1),1));
						g[enc(y,x+1)].push_back(Edge(enc(y,x+1),enc(y,x),1));
					}
				}
			}else{
				REP(x,W){
					int b;cin >> b;
					if(b==0){
						g[enc(y,x)].push_back(Edge(enc(y,x),enc(y+1,x),1));
						g[enc(y+1,x)].push_back(Edge(enc(y+1,x),enc(y,x),1));
					}
				}
			}
		}
        int d=dijkstra(g,enc(0,0))[enc(H-1,W-1)];
		if(d<INF)cout << d+1<<endl;
		else cout << 0 <<endl;
	}
}

Measured memory_bytes: 1280
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    inf=10**6
    N,K=MI()
    P=LI()
    inf=10**6
    class SegTree:
        def __init__(self,N,ide,segfunc=min):
            self.ide_ele = ide
            """
            ex)
             最小値のセグ木 → +inf
              和のセグ木 → 0
              積のセグ木 → 1
              gcdのセグ木 → 0
            """
            
            self.segfunc=segfunc
            
            #num:N以上の最小の2のべき乗
            self.num =2**(N-1).bit_length()
            self.seg=[self.ide_ele]*2*self.num




        #リストで初期化する
        def setL(self,init_val):
            #init_valは操作する数列
            for i in range(N):
                self.seg[i+self.num-1]=init_val[i]    
            #built
            for i in range(self.num-2,-1,-1) :
                self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 


        #k番目の値をxに更新
        def update(self,k,x):
            k += self.num-1
            self.seg[k] = x
            while k:
                k = (k-1)//2
                self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])


        #[p,q)の区間に対するクエリへの応答
        def query(self,p,q):
            if q<=p:
                return self.ide_ele
            p += self.num-1
            q += self.num-2
            res=self.ide_ele
            while q-p>1:
                if p&1 == 0:
                    res = self.segfunc(res,self.seg[p])
                if q&1 == 1:
                    res = self.segfunc(res,self.seg[q])
                    q -= 1
                p = p//2
                q = (q-1)//2
            if p == q:
                res = self.segfunc(res,self.seg[p])
            else:
                res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
            return res



    
    """
    長さKの尺取りぽく見るか．
    最小値が抜けて最大値が入る場合は不変．
    ただし，並び替え後も元の物と変わらない場合を何度かカウントしそう．
    事前に（元から昇順になっている長さKの列）の個数を数えておこうか．
    後からこれを引くのはダメ，事前に計算しておかないと，すでに照準になっているものを数えているのか数えていないのか不明になる．
    
    これは簡単に求まる．次が自分以上なら1をつけて，長さKの尺取りで和がKならおk．
    累積和の方が実装が楽かなあ
    """
    ans=1#最初のK個を並び替えたものは無条件で数える
    mseg=SegTree(N,inf,min)
    Mseg=SegTree(N,-1,max)
    mseg.setL(P)
    Mseg.setL(P)
    
    #累積和パート
    S=[0]*(N+1)
    for i in range(N-1):
        if P[i]<P[i+1]:
            S[i+1]=1
    #print(S)
            
    for i in range(N):
        S[i+1]+=S[i]
    
    m=min(P[:K])
    M=max(P[:K])
    cnt=0#最初と同じ配列のものを何回数えたか
    if S[K]==K:#最初のKこを並び替えたものを1回とすでに数えてしまっているのでチェック
        cnt+=1
        
    for i in range(K,N):
        if m==P[i-K] and P[i]>M:#最小値が抜けて，新しく入るのが最大値を更新するなら
            m=mseg.query(i-K+1,i+1)
            M=P[i]
        else:
            m=mseg.query(i-K+1,i+1)
            M=Mseg.query(i-K+1,i+1)
            #print(i,S[i]-S[i-K+1],S[i],S[i-K+1])
            if cnt==0:
                ans+=1
            elif S[i]-S[i-K+1]!=(K-1):
                ans+=1
            if S[i]-S[i-K+1]==(K-1):
                cnt+=1
                
        #print(i,m,M,ans,cnt)

            
    print(ans)
    #print(S)

main()


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

typedef long long ll;

    ll m, n;
    ll w[110];
    
    bool check(ll mid){
        ll sum=0, count=1;
        for(ll i=1; i<=n; i++){
            if(w[i]>mid)    return false;
            sum+=w[i];
            if(sum>mid){
                count++;
                sum=w[i];
            }
        }
        return count<=m;
    }
    
int main(void){
    while(cin >> m >> n){
        if(m+n==0) break;
        for(int i=1; i<=n; i++){
            cin >> w[i];
        }
        ll under=0, upper=1500000;
        while(upper-under>1LL){
            ll mid=(under+upper)/2;
            
            if(! check(mid)){
                under=mid;
            }
            else{
                upper=mid;
            }
        }
    
        cout << upper << "\n";
    }
    
    return 0;
}


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

int main(void)
{
  unsigned long long N, i,j;
  unsigned long long a = INFINITY, b = INFINITY;
  double C;
  scanf("%llu", &N);
  //N = 10000000019;
  for (i = 1; i <= sqrt(N); i++)
  {
    C = N / i;
    if(N % i == 0){
      j = N / i;
      if(i + j < a + b - 2){
        a = i;
        b = j;
      }
    }
  }
  //printf("%llu %llu ", a, b);
  printf("%llu", a + b - 2);
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
 
using namespace std;
typedef long long int lli;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef pair <lli,lli> pii;
#define ff first
#define ss second
#define MOD 1000000007
#define pb push_back
 
int main(){
	fast;
  	double n;
  	cin>>n;
  	int ans=ceil(n/((double)(2)));
  	cout<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int h,m,s;

    h = a / 3600;
    a %= 3600;

    m = a / 60;
    a %= 60;

    s = a;

    System.out.println(h + ":" + m + ":" + s);   

       
   
  }

}

Measured memory_bytes: 26204
#include <iostream>
using namespace std;
int main()
{
    long long n, a, b, xbef, xaft, x, ans = 0;
    cin >> n >> a >> b >> xbef;
    for(int i = 1; i < n; i++){
        scanf("%lld", &xaft);
        x = xaft - xbef;
        ans += (x * a < b ? x * a : b);
        xbef = xaft;
    }
    cout << ans << endl;
    return 0;
}

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

#define N 200010
int n, a[N], b[N];

bool ok() {
    for (int i = 1; i <= n; ++i) {
        int tot = 0;
        for (int j = i; j <= n; j += i) {
            tot = tot + b[j];
            tot %= 2;
        }
        if (tot ^ a[i]) return 0;
    }
    return 1;
}

int main() {
    while (scanf("%d", &n) != EOF) {
        for (int i = 1; i <= n; ++i) scanf("%d", a + i);
        for (int i = n; i >= 1; --i) {
            int now = 0;
            for (int j = i + i; j <= n; j += i) {
                now += b[j];
                now %= 2;
            }
            b[i] = now ^ a[i];
        }
        if (ok()) {
            vector <int> vec;
            for (int i = 1; i <= n; ++i) if (b[i]) vec.push_back(i);
            int sze = (int)vec.size();
            printf("%d\n", sze);
            for (int i = 0; i < sze; ++i) printf("%d%c", vec[i], " \n"[i == sze - 1]);
        } else puts("-1");
    }
    return 0;
}

Measured memory_bytes: 3064
program main
   implicit none
   integer(8) ::i,j,k,le
   character*200000 s
   integer(8) ::counter=0,acount=0,dummy
!   integer,allocatable,dimension(:)::
   read(*,*)s
   le=len_trim(s)
   do i=1,le
      if(s(i:i)=="B")then
         acount=acount+i
      else
         counter=counter+1
      endif
   enddo
   write(*,*)(le-counter)*(le+counter+1)/2-acount
end program main


Measured memory_bytes: 1340
N = int(input())
H = list(map(int,input().split()))

for i in range(N-1,1,-1):
    H0=H[i]-H[i-1]
    if H0 <= -2:
        print("No")
        exit()
    elif H0 == -1:
        H[i-1] -= 1

    
print("Yes")

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

typedef long long ll;
const ll INF = 1010000000000000017LL;
const ll MOD = 1000000007LL;

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

//#define DEBUG(fmt, ...)
#define DEBUG(fmt, ...) fprintf(stderr, fmt "\n", ##__VA_ARGS__)

int main(){
    std::cout<<std::fixed<<std::setprecision(10);

    ll N;
    cin >> N;

    ll count = 0;
    REP(i, N){
        string s = to_string(i+1);
        if( s.size() % 2 == 1 ) count++;
    }
    cout << count << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) prllf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

ll gcd(ll x, ll y) {
    if(y == 0) {
        return x;
    }
    return gcd(y, x%y);
}

class Monoid {
public:
    // 単位元
    ll unit;

    Monoid() {
        // 単位元
        unit = 0;
    }
    
    // 演算関数
    ll calc(ll a, ll b) {
        return gcd(a, b);
    }
};
 
class SegmentTree {
public:
    ll n;  // セグメント木の葉の要素数
    vector<ll> tree;  // セグメント木
    Monoid mono;  // モノイド
    
    SegmentTree(vector<ll> &v) {
        n = 1 << (ll)ceil(log2(v.size()));
        tree = vector<ll>(n << 1);
        for(ll i = 0; i < v.size(); i++) {
            update(i, v[i]);
        }
        for(ll i = v.size(); i < n; i++) {
            update(i, mono.unit);
        }
    }
    
    // k番目の値(0-index)をxに変更
    void update(ll k, ll x) {
        k += n;
        tree[k] = x;
        for(k = k >> 1; k > 0; k >>= 1){
            tree[k] = mono.calc(tree[k << 1 | 0], tree[k << 1 | 1]);
        }
    }
    
    // [l, r)(0-index)で演算をする
    ll query(ll l, ll r) {
        ll res = mono.unit;
        l += n;
        r += n;
        while(l < r) {
            if(l & 1) {
                res = mono.calc(res, tree[l++]);
            }
            if(r & 1) {
                res = mono.calc(res, tree[--r]);
            }
            l >>= 1;
            r >>= 1;
        }
        return res;
    }

    ll operator[](ll k) {
        // seg[i]で添字iの要素の値を返す
        if(k - n >= 0 || k < 0) {
            return -INF;
        }
        return tree[tree.size()-n+k];
    }
    
    void show() {
        ll ret = 2;
        for(ll i = 1; i < 2*n; i++) {
            cout << tree[i] << " ";
            if(i == ret - 1) {
                cout << endl;
                ret <<= 1;
            }
        }
        cout << endl;
    }
};

int main() {
    ll n;
    cin >> n;
    
    vl a(n);
    rep(i, n) {
        cin >> a[i];
    }
    
    ll ans = 0;
    SegmentTree seg(a);
    rep(i, n) {
        ll u = seg[i];  // uにa[i]をコピーする
        seg.update(i, 0);  // a[i]を0(gcdの単位元)に更新する
        chmax(ans, seg.query(0, n));  // aの[0,n)でのgcdを求める
        seg.update(i, u);  // a[i]を元の値に戻す
    }

    out(ans);
    re0;
}

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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define PI 3.14159265358979
#define MOD 1000000007 // = 10^9 + 7

using namespace std;
using ll = long long;

void solve()
{
	int n;
	cin >> n;

	for(int i = 1; i <= 9; ++i)
	{
		if (n % i == 0 && n / i <= 9)
		{
			cout << "Yes";
			return;
		}
	}
	cout << "No";
}

int main()
{
	fastio;
	solve();

	return 0;
}

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

using namespace std;

class DisjointSet{
public:
    vector<int> p,rank;
    
    DisjointSet();
    DisjointSet(int size){
        rank.resize(size,0);
        p.resize(size,0);
        for(int i = 0;i < size;++i){
            makeSet(i);
        }
    }
    
    void makeSet(int x){
        p[x] = x;
        rank[x] = 0;
    }
    
    bool same(int x,int y){
        return findSet(x) == findSet(y);
    }
    
    void unite(int x,int y){
        link(findSet(x),findSet(y));
    }
    
    void link(int x,int y){
        if(rank[x] > rank[y]){
            p[y] = x;
        }else{
            p[x] = y;
            if(rank[x] == rank[y]){
                rank[y]++;
            }
        }
    }
    
    int findSet(int x){
        if(x != p[x]){
            p[x] = findSet(p[x]);
        }
        return p[x];
    }
};

class Edge{
public:
    int source,target,cost;
    Edge(int source = 0,int target = 0,int cost = 0):
    source(source),target(target),cost(cost){}
    
    bool operator < (const Edge &e) const {
        return cost < e.cost;
    }
};

int kruskal(int n,vector<Edge> edges){
    int totalCost = 0;
    sort(edges.begin(),edges.end());
    
    DisjointSet dSet = DisjointSet(n + 1);
    
    for(int i = 0;i < n;++i){
        dSet.makeSet(i);
    }

    for(int i = 0;i < edges.size();++i){
        Edge e = edges[i];
        if(!dSet.same(e.source,e.target)){
            totalCost += e.cost;
            dSet.unite(e.source,e.target);
        }
    }
    return totalCost;
}

int main(){
    int n,m,cost,source,target;
    vector<Edge> edges;
    cin >> n >> m;
    
    for(int i = 0;i < m;++i){
        cin >> source >> target >> cost;
        edges.push_back(Edge(source,target,cost));
    }
    cout << kruskal(n,edges) << endl;
}


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

int main(){
    int k, s;
    cin >> k >> s;
    int ans = 0;
    for(int i=0;i<=k;++i){
        for(int j=0;j<=k;++j){
            int l = s - i - j;
            if(l >= 0 && l <= k)ans++;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val list = readLine()?.split(" ") ?: listOf()
    val a = Integer.parseInt(list[0] ?: "0")
    val b = Integer.parseInt(list[1] ?: "0")
    val t = Integer.parseInt(list[2] ?: "0")
  
    val cnt = ((t + 0.5f) / a).toInt()
    println(cnt * b)
}


Measured memory_bytes: 38024
N, K = map(int, input().split())
R, S, P = map(int, input().split())
#point = {'r':P, 's':R, 'p':S}
#print(point)
T = input()

r_num = 0
s_num = 0
p_num = 0

mycurrent = ['a' for _ in range(K)]

for n in range(N):
    if T[n] == 'r':
        me = 'p'
    if T[n] == 's':
        me = 'r'
    if T[n] == 'p':
        me = 's'
    
    if mycurrent[n%K] != me:
        if me == 'r':
            r_num += 1
            mycurrent[n%K] = me
        if me == 's':
            s_num += 1
            mycurrent[n%K] = me
        if me == 'p':
            p_num += 1
            mycurrent[n%K] = me
            
    else:
        mycurrent[n%K] = 'a'
        
    #print(r_num, s_num, p_num)
print(r_num* R + s_num* S + p_num*P)

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n; cin >> n;
    vector<int> d(n);
    for (int i = 0; i < n; i++) {
        cin >> d[i];
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            ans += d[i] * d[j];
        }
    }
    cout << ans << '\n';
}



Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
using namespace std;
const int mod = 1000000007;
#define ll long long

int main()
{
	int N, A[100010];
	int ans = 0;
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> A[i];
	A[0] = 0; A[N + 1] = 0;
	for (int i = 0; i < N + 1; i++) {
		ans += abs(A[i + 1] - A[i]);
	}
	int tmp = ans;
	for (int i = 1; i <= N; i++) {
		ans = tmp;
		ans -= abs(A[i + 1] - A[i]);
		ans -= abs(A[i] - A[i - 1]);
		ans += abs(A[i + 1] - A[i - 1]);
		cout << ans << endl;
	}
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
#define rep(i,n) for(i=0;i<(n);i++)
using namespace std;
using ll=long long;
using P=pair<int,int>;
int main() {
  string s;
  cin >> s;
  
  int t = 0;
  for (char c : s) {
    t += (c - '0');
  }
  
  t %= 9;
  if (t == 0) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 3744
#include <iostream>
#include <math.h>
#include<iomanip>
using namespace std;

int main(){
  int A=0,B=0,C=0,D=0,E=0,F=0,G=0,H=0,I=0,J=0,K=0,L=0,M=0,N=0,O=0,P=0,Q=0,R=0,S=0;
  int A2=0,A3=0,B2=0,B3=0;
  cin >>N;
  A=N*100/108;
  A2=N*100/108+1;
  A3=N*100/108-1;
  B=A*108/100;
  B2=A2*108/100;
  B3=A3*108/100;
  if(B==N){
    cout << A << endl;
  }
  else if(B2==N){
    cout << A2 << endl;
  }
  else if(B3==N){
    cout << A3 << endl;
  }
  else cout << ":(" << endl;

  
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
  
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

using namespace std;

int inputValue(){
    int a;
    cin >> a;
    return a;
};

void inputArray(int * p, int a){
    rep(i, a){
        cin >> p[i];
    }
};

void inputVector(vector<int> * p, int a){
    rep(i, a){
        int input;
        cin >> input;
        p -> push_back(input);
    }
}
  
int main()
{
    int i,j;
    ll tmp=0, ans=0;
  ll n; cin >> n;
  ll h[n];
  rep(i,n){cin >> h[i];}

  for(i=n-2;i>=0;i--){
      if(h[i]>=h[i+1]){tmp++;}else{tmp=0;}
      if(tmp>ans){ans=tmp;}
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define aall(x,n) (x).begin(),(x).begin()+(n)
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define sum accumulate
#define keta fixed<<setprecision
#define vvector(name,t,m,n,a)vector<vector<t> > name(m,vector<t> (n,a))
#define vvvector(name,t,l,m,n,a) vector<vector<vector<t> > > name(l, vector<vector<t> >(m, vector<int>(n,a)));
typedef long long ll;
const int INF = 100000000;
const long INF64 = 1000000000000000ll;
const ll MOD = 998244353LL;
int main(){
	int n,m;
	std::cin >> n>>m;
	vvector(a,int,n+1,m+1,0) ;
	rep(i,n)rep(j,m){
		std::cin >> a[i][j];
	}

	rep(i,n){
		int ans=0;
		rep(j,m){
			ans+=a[i][j];
			
		}
		a[i][m]=ans;
	}
	//	std::cout << "hoge" << std::endl;
	rep(i,m+1){
		int ans=0;
		rep(j,n){
			ans+=a[j][i];
			//std::cout << i<<j << std::endl;
		}
		
		a[n][i]=ans;
//		std::cout << i << std::endl;
	}
//	std::cout << a[n][m] << std::endl;
	rep(i,n+1){
		rep(j,m+1){
			std::cout << a[i][j];
			if(j!=m)std::cout << " ";// << std::endl;
		
		}
	
		std::cout << std::endl;
		
	}
}


Measured memory_bytes: 3140