akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    ll n;
    string s;
    cin >> n >> s;
    ll q;
    cin >> q;
    rep(i,q){
        ll k;
        cin >> k;
        ll now = 0;
        ll d = 0, m = 0, dm = 0;
        ll ans = 0;
        while(now < n){
            if(s[now] == 'D') ++d;
            else if(s[now] == 'M'){
                ++m;
                dm += d;
            }else if(s[now] == 'C'){
                ans += dm;
            }
            if(now - k + 1 >= 0){
                j = now - k + 1;
                if(s[j] == 'D'){
                    dm -= m;
                    --d;
                }
                else if(s[j] == 'M') --m;
            }
            ++now;
        }
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 5240
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)n;i++)
using Graph = vector<vector<int> >;
using GraphC = vector<vector<char> >;
const int INF = 1000000000;
typedef pair<int, int> P;
const int MAX_N = 1000000000;
typedef int64_t ll;
template<class T> inline bool chmax(T & a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T & a, T b) { if (a > b) { a = b; return 1; } return 0; }




int main() {
	string S;
	cin >> S;
	
	if (S.at(0) != 'A') {
		cout << "WA" << endl;
		return 0;
	}

	int cnt = 0;
	int check;
	for (int i = 2; i < S.size()-1; i++)
	{
		if (S.at(i)=='C')
		{
			cnt++;
			check = i;
		}
	}

	if (cnt==1)
	{
		for (int i = 1; i < S.size(); i++)
		{
			if (i == check)continue;
			
			if (S.at(i)< 'a' || S.at(i)>'z')
			{
				cout << "WA" << endl;
				return 0;
			}

			
		}
		cout << "AC" << endl;
		return 0;
	}
	cout << "WA" << endl;
	return 0;
}

Measured memory_bytes: 3604
A, B = list(map(int, input().split()))

ans = 0
a = A // 0.08 + 1
b = B // 0.1 + 1
c = max(a, b)
if int(c * 0.08) == A and int(c * 0.1) == B:
    ans = int(c)
else:
    ans = "-1"
print(ans)

Measured memory_bytes: 3060
# 入力
n, k = map(int, input().split())
A = [] # 寿司のネタの美味しさと種類を入れるリスト
for _ in range(n):
    A.append(list(map(int, input().split())))

# 美味しさ順にソートする
A.sort(key=lambda x: x[1], reverse=True)

# 美味しさで貪欲にとる
X = [] # 同じ種類で他に美味しさの大きい寿司が存在する
Y = [] # 取った寿司の中の各々の種類で美味しさが最も大きい
st = set() # 種類
for i in range(k):
    t, d = A[i]
    if t in st:
        X.append(d)
    else:
        Y.append(d)
        st.add(t)

# 美味しさポイントを求める
x = sum(X)
y = sum(Y)
v = len(Y) # 種類数
ans = x + y + v ** 2
for i in range(k, n):
    if not X:
        break
    t, d = A[i]
    if t in st:
        continue
    st.add(t)
    x -= X.pop()
    y += d
    v += 1
    ans = max(ans, x + y + v ** 2)

print(ans)

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

int main(){
    long long S; cin >> S;
    long long X2, Y2, X3, Y3;

    X2 = 1e9;
    Y2 = 1;

    Y3 = (S + X2 - 1) / X2;
    X3 = X2 * Y3 - S;

    cout << 0 << " " << 0 << " " << X2 << " " << Y2 << " " << X3 << " " << Y3 << endl;   
}

Measured memory_bytes: 256
// problem: "https://atcoder.jp/contests/abc153/tasks/abc153_c"

#include<bits/stdc++.h>
#define ll long long

using namespace std;

int main()
{
    ll n,k;
    cin>>n>>k;

    vector<ll>V(n);
    int i;

    for(i=0;i!=n;i++)
        cin>>V[i];

    sort(V.begin(),V.end(),greater<ll>());

    ll sum = 0;
    for(i=k;i<n;i++)
        sum += V[i];

    cout<<sum;

    return 0;
}


Measured memory_bytes: 1920
N = int(input())
A = list(map(int, input().split()))
if N%2 == 0:
    I = [i for i in range(N-1, 0, -2)] + [i for i in range(0, N, 2)]
else:
    I = [i for i in range(N-1, -1, -2)] + [i for i in range(1, N, 2)]
for i in I:
    print(A[i], end=' ')

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

using namespace std;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  while(s.length() > 2){
    s.pop_back();
    if(s.length() % 2) continue;
    string a = "", b = "";
    for(int i=0; i<s.length()/2 ;i++) a += s[i];
    for(int i=s.length()/2; i<s.length(); i++) b += s[i];
    if(a == b) break;
  }
  cout << s.length() << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (ll i=0; i < (n); ++i)
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; }
template<class T> inline bool change(T& a, T b) { if (a != b) { a = b; return 1; } return 0; }
using namespace std;
typedef long long ll;

//株・金
map<ll,ll> dp[100];
ll a[100];
ll n;

int main(){
    cin >> n;
    for(ll i=1;i<=n;i++) cin >> a[i];
    dp[1][0]=1000;
    for(ll i=1;i<=n;i++){
        for(const auto& [j, mon] :dp[i]){
            chmax(dp[i+1][j],mon);
            chmax(dp[i+1][0],mon+a[i]*j);
            chmax(dp[i+1][j+mon/a[i]],mon%a[i]);
        }
    }
    cout << dp[n+1][0] << endl;
}

Measured memory_bytes: 3836
K, A, B = map(int, input().split())

ans = 1
if (B - A) > 2:
    ans = A
    if (K - (A - 1)) % 2 == 0:
        ans += (B - A) * int((K - (A - 1)) / 2)
    else:
        ans += (B - A) * int((K - (A - 1)-1) / 2) + 1
else:
    ans += K
print(ans)

Measured memory_bytes: 3060
def resolve():
    import sys
    sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
    to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
    print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

    # 入力を整数に変換して受け取る
    def input_int(): return int(input())

    def map_int_input(): return map(int, input())

    MII = map_int_input

    def MII_split(): return map(int, input().split())

    def MII_to_index(): return map(to_index, input())

    def MII_split_to_index(): return map(to_index, input().split())

    # 入力全てを整数に変換したものの配列を受け取る
    def list_int_inputs(): return list(map(int, input()))

    LII = list_int_inputs

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

    # 2次元リスト化
    def LII_2D(rows_number): return [LII() for _ in range(rows_number)]

    def LII_split_2D(rows_number): return [LII_split() for _ in range(rows_number)]

    N, K = MII_split()
    ps = LII_split()

    import numpy as np
    ps_array = np.array(ps)
    indicies = np.argsort(ps_array)
    print(sum([ps[i] for i in indicies[:K]]))
    
resolve()

Measured memory_bytes: 27244
alphabet = {
    "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,
    "t" => 0,
    "u" => 0,
    "v" => 0,
    "w" => 0,
    "x" => 0,
    "y" => 0,
    "z" => 0
}

loop do
    input = gets
    if input == nil
        break
    else
        input = input.chomp.downcase.split("").map do |s| s.to_s end
        input.each do |n|
            alphabet[n] = alphabet[n].to_i + 1
        end
    end
end

("a".."z").each do |n|
    puts "#{n} : #{alphabet[n]}"
end

Measured memory_bytes: 8704
N, K = map(int, input().split())
P_L = [int(x)-1 for x in input().split()]
C_L = [int(x) for x in input().split()]

ans = float("-Inf")
for s in range(N):
    _s_l = []
    _v = s
    _cumsum = 0
    _ans = float("-Inf")
    while True:
        _nextv = P_L[_v]
        _cumsum += C_L[_nextv]
        _s_l.append(_cumsum)
        _v = _nextv
        if _nextv == s:
            break
    if K <= len(_s_l):
        _ans = max(_s_l[:K])
    else:
        if _s_l[-1] < 0:
            _ans = max(_s_l)
        else:
            _l = len(_s_l)
            if K % _l == 0:
                _ans = max(_s_l[-1] * (K // _l),
                           _s_l[-1] * (K // _l - 1) + max(_s_l))
            else:
                _ans = max(_s_l[-1] * (K // _l) + max(_s_l[:K % _l]),
                           _s_l[-1] * (K // _l - 1) + max(_s_l))
    ans = max(ans, _ans)

print(ans)


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

int main()
{
ll n ;
cin >> n ;
string s ;
cin >> s ;
char a=s[0];
s+='A';
rep(i,n){
  if(s[i+1]!=a){
    ans++;
    a=s[i+1];
  }
}
cout << ans << endl;
return 0;
}

Measured memory_bytes: 512
#include<stdio.h>
int main(void){
 int i,last;
 int tests[10000];
 for(i=0;i<=10000;i++){
  scanf("%d",&tests[i]);
  if(tests[i]==0){
    last=i-1;
    break;
  }
 }
 for(i=0;i<=last;i++){
   printf("Case %d: %d\n",i+1,tests[i]);
 }
 return(0);
}

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

template<typename H> bool chmin(H& v1, const H v2) { if (v1 > v2) { v1 = v2; return true; } return false; }
template<typename H> bool chmax(H& v1, const H v2) { if (v1 < v2) { v1 = v2; return true; } return false; }
template<typename H> void read(H& head) { cin >> head; }
template<typename H, typename ...T> void read(H& head, T& ...tail) { cin >> head; read(tail...); }
template<typename H> void print(H head) { cout << head << '\n'; }
template<typename H, typename ...T> void print(H head, T ...tail) { cout << head << " "; print(tail...); }

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	ll n, k;
	read(n, k);
	ll ans = 1;

	map<ll, int> m;

	for (ll i = 2; i * i <= k; i++) {
		while (k % i == 0) m[i]++, k /= i;
	}
	if (k > 1) m[k]++;

	for (auto p : m) rep(i, 0, p.second / n) ans *= p.first;
	cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef pair<P,int> T;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define LLINF 1000000000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
int N,M;
int A[100100],B[100100];
int deg[100100];
vector<int> g[100100];
bool used[100100];
void add_edge(int a,int b){
	g[a].pb(b);
	g[b].pb(a);
	deg[a]++;
	deg[b]++;
}
void dfs(int v,vector<int> &ans){
	used[v] = true;
	ans.pb(v);
 	for(int i=0;i<g[v].size();i++){
		int u = g[v][i];
		if(used[u])continue;
		dfs(u,ans);
		break;
	}
}
int main(){
	cin >> N >> M;
	for(int i=0;i<M;i++){
		cin >> A[i] >> B[i];
		A[i]--;B[i]--;
		add_edge(A[i],B[i]);
	}
	for(int i=0;i<N;i++){
		if(deg[i]==1){
			vector<int> ans;
			dfs(i,ans);
			cout << ans.size() << endl;
			for(int i=0;i<ans.size();i++){
				cout << ans[i]+1;
				if(i<ans.size()-1)cout << ' ';
				else cout << endl;
			}
			return 0;
		}
	}
	used[0]=true;
	vector<int> A,B;
	int a = 0;
	int b = -1;
	dfs(a,A);
	for(int i=0;i<g[a].size();i++){
		if(!used[g[a][i]]){
			b = g[a][i];
			break;
		}
	}
	if(b!=-1){
		dfs(b,B);
		reverse(all(A));
		cout << A.size()+B.size() << endl;
		for(int i=0;i<A.size();i++){
			cout << A[i]+1 << ' ';
		}
		for(int i=0;i<B.size();i++){
			cout << B[i]+1;
			if(i<B.size()-1)cout << ' ';
			else cout << endl;
		}
		return 0;
	}else{
		cout << A.size() << endl;
		for(int i=0;i<A.size();i++){
			cout << A[i]+1 << ' ';
		}
	}
	return 0;
}

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

int main(void)
{
	int a, b, c, max, mid, min;
	scanf("%d%d%d", &a, &b, &c);

	max = a;
	if (b > max) max = b;
	if (c > max) max = c;

	min = a;
	if (b < min) min = b;
	if (c < min) min = c;

	mid = a + b + c - min - max;

	printf("%d\n", max * 10 + mid + min);
	return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Solve s= new Solve();
		s.solve();
	}

}
class Solve{
	 Scanner sc = new Scanner(System.in) ;

	 void solve() {
	 int s=sc.nextInt();
	 int a,b;
	 boolean res=true;
	 b=99;
	 for(int i=0;i<4;i++) {
		 a=s%10;
       	s=s/10;
		 if(a==b) {
			 res=false;
		 }
		 b=a;
	 }
	 if(res==true) {
		 System.out.println("Good");
	 }else {
		 System.out.println("Bad");
	 }
	 }
}

Measured memory_bytes: 21844
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	//	"strings"
)

func main() {
	sc := NewScanner()

	n := sc.NextInt()
	m := sc.NextInt()

	mp := map[int]struct{}{}
	for i := 0; i < m; i++ {
		tmp := sc.NextInt()
		mp[tmp] = struct{}{}
	}
	dp := make([]int64, n+1)
	dp[0] = 1
	dp[1] = 1
	if _, ok := mp[1]; ok {
		dp[1] = 0
	}
	for i := 2; i <= n; i++ {
		dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
		if _, ok := mp[i]; ok {
			dp[i] = 0
		}
	}
	fmt.Printf("%v\n", dp[n]%1000000007)
}

type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r: rdr}
}
func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *Scanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}

func (s *Scanner) NextIntArray() []int {
	s.pre()
	start := s.p
	result := []int{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			result = append(result, v)
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	result = append(result, v)

	return result
}

func (s *Scanner) NextMap() map[int]bool {
	s.pre()
	start := s.p
	mp := map[int]bool{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			mp[v] = true
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	mp[v] = true

	return mp
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}


Measured memory_bytes: 4608
#include <cstdio>
#include <vector>

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

typedef std::vector<int> v;
typedef std::vector<std::vector<int>> vv;

int main(void)
{
    int n, m;
    scanf("%d %d", &n, &m);

    v hh(n);
    rep(i, n)
    {
        int h;
        scanf("%d", &h);
        hh[i] = h;
    }

    vv ggg(n);

    rep(i, m)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        ggg[a - 1].push_back(b);
        ggg[b - 1].push_back(a);
    }

    v aa(n);
    rep(i, n)
    {
        int p = hh[i];
        for (auto x : ggg[i])
        {
            if (p >= hh[x - 1])
                aa[x - 1] = 1;
        }
    }

    int ans = 0;
    rep(i, n)
    {
        if (!aa[i])
            ++ans;
    }

    printf("%d", ans);
}

Measured memory_bytes: 8676
#include<bits/stdc++.h>
using namespace std;
signed main(){
  int a,b,c[200],d=0,z=0;
  cin>>a>>b;
  for(int i=0;i<a;i++){
    cin>>c[i];
    d=c[i]+d;
    if(d<=b){
      z++;
    }
  }
  cout<<z+1<<"\n";
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define div1 1000000007
const long long INF = 1LL << 60;
using namespace std;
typedef long long ll;
typedef long double ld;
// a>b -> a==b;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
// a<b -> a==b;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

int main(void)
{
    ll a, b, c, d, turn=1;

    cin >> a >> b >> c >> d;

    while(a>0 && c>0){
        if(turn%2==1) c -= b;
        else a -= d;

        if(a<=0){
            cout << "No" << endl;
            return 0;
        }
        if(c<=0){
            cout << "Yes" << endl;
            return 0;
        }

        turn++;
    }

    return 0;
}

Measured memory_bytes: 3624
s = int(input())
L = s//100
R =s%100

if 1 <= L <=12:
    if 1<= R <= 12:
        print('AMBIGUOUS')
    else:
        print('MMYY')
else:
    if 1<= R <=12:
        print('YYMM')
    else:
        print('NA')

Measured memory_bytes: 3060
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 66666
int n,ans=2e9;
char s[SZ],t[SZ];
void wo(vector<pii> a,vector<pii> b)
{
	if(a.size()>b.size())
	{
		wo(b,a);
		return;
	}
	reverse(a.begin(),a.end());
	while(a.size()<b.size()) a.pb(mp(0,!a.back().se));
	reverse(a.begin(),a.end());
	if(a.back().se!=b.back().se) return;
	if(a.size()!=b.size()) throw "GG";
	int su=0;
	for(int i=0;i<a.size();++i)
		su+=abs(a[i].fi-b[i].fi);
	ans=min(ans,su);
}
int main()
{
	cin>>n>>(s+1)>>(t+1);
	for(int i=1;i<=n;++i) s[i]-='0',t[i]-='0';
	if(n<=2)
	{
		int su=0;
		for(int i=1;i<=n;++i)
			su+=s[i]!=t[i];
		printf("%d\n",su);
		return 0;
	}
	vector<pii> p,q,qq;
	for(int i=1;i<n;++i)
	{
		if(s[i]!=s[i+1]) p.pb(mp(i,s[i]));
		if(t[i]!=t[i+1]) q.pb(mp(i,t[i]));
	}
	qq=q;
	for(int i=0;i<=n+10;++i)
	{
		wo(p,qq); qq.pb(mp(n,!qq.back().se));
	}
	for(int i=0;i<=n+10;++i)
	{
		wo(p,q); p.pb(mp(n,!p.back().se));
	}
	cout<<ans<<"\n";
}


Measured memory_bytes: 1016
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_map>
#include<climits>
#include<cstdlib>
#include<cmath>
#include<string>
#include<iomanip>
#include<bitset>

using namespace std;

#define ll long long int

ll const MOD = 1000000007;
ll const INF = (long long int)1 << 61;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll n,w;
    cin >> n >> w;

    vector<vector<ll>> in(n,vector<ll>(2));
    for(int i = 0; i < n; i++){
        cin >> in[i][0] >> in[i][1];
    }

    vector<vector<ll>> dp(n+1,vector<ll>(w+1,0));

    for(int i = 0; i < n; i++){
        for(int j = 0; j <= w; j++){
            dp[i+1][j] = dp[i][j];
        }
        for(int j = 0; j <= w; j++){
            if(j + in[i][0] <= w){
                dp[i+1][j + in[i][0]] = max(dp[i+1][j + in[i][0]],dp[i][j] + in[i][1]);
            }
        }
    }

    cout << dp[n][w] << endl;
    
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < n; ++i)
#pragma region Debug
template <typename T>
void view(const std::vector<T> &v)
{
    for (const auto &e : v)
    {
        std::cout << e << " ";
    }
    std::cout << std::endl;
}
template <typename T>
void view(const std::vector<std::vector<T>> &vv)
{
    for (const auto &v : vv)
    {
        view(v);
    }
}
#pragma endregion

int main()
{
    int n, d, a;
    cin >> n >> d >> a;
    vector<P> mons(n, P(0, 0));
    vector<ll> dec(n + 1, 0);
    rep(i, n) cin >> mons[i].first >> mons[i].second;

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

    ll ans = 0;

    int j = 0;
    rep(i, n)
    {
        P now = mons[i];
        while (j < n && mons[j].first <= now.first + 2 * d)
        {
            j++;
        }

        now.second -= a * dec[i];
        int times = (now.second + a - 1) / a;
        times = max(times, 0);
        ans += times;
        dec[i] += times;
        // since the condition in the loop holds up to j-1
        // monster j does not get hit, but we increment anyways with the dp.
        // To account for this, subtract from monster j so all monsters up to j-1 "gets hit"
        // but monster j doesn't receive this damage because we subtract
        dec[j] -= times;
        dec[i + 1] += dec[i];
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4992
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include <numeric>
using namespace std;
#define INF (1 << 30) - 1
#define LINF 1LL << 60
const int MOD = 1000000007;
using ll = long long;
using P = pair<int, int>;

int main(){
  int n;
  ll z, w;
  cin >> n >> z >> w;
  vector<ll> a(n);
  for(int i = 0; i < n; ++i){
  	cin >> a[i];
  }

  ll ans = abs(a[n - 1] - w);
  if(n >= 2)ans = max(ans, abs(a[n - 2] - a[n - 1]));
  cout << ans << endl;
  
  return 0;
}


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

int main() {
	int x,y;
	cin >> x >> y;
    int ans = 0;
    vector<int>vec = {1,3,5,7,8,10,12};
    vector<int>usi = {4,6,9,11};
    for(int i = 0; i < 7; i++){
      for(int j = 0; j < 7; j++){
      if(x == vec[i] && y == vec[j]){
        ans++;
      }
      }
    }
    for(int i = 0; i < 4; i++){
      for(int j = 0; j < 4; j++){
      if(x == usi[i] && y == usi[j]){
        ans++;
      }
      }
    }
   if(x == 2 || y == 2){
     cout << "No" << endl;
   }
   else if(x == y){
     cout << "Yes" <<endl;
   }
   else if(ans >= 1){
     cout << "Yes" <<endl;
   }
   else{
     cout << "No" << endl;
   }
}



Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pqueue priority_queue
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int DP[1005][10005];

int main() {
  int H, N;
  cin>>H>>N;
  int A[N], B[N];
  for(int i=0;i<N;++i) cin>>A[i]>>B[i];
  for(int j=1;j<=H;++j) {
    if(j%A[0]==0) DP[0][j] = (j/A[0])*B[0];
    else DP[0][j] = (j/A[0]+1)*B[0];
  }
  for(int i=1;i<N;++i) {
    for(int j=1;j<=H;++j) {
      if(j<=A[i]) DP[i][j] = min(DP[i-1][j], B[i]);
      else DP[i][j] = min(DP[i-1][j], min(DP[i][j-A[i]]+B[i], DP[i-1][j-A[i]]+B[i]));
    }
  }
  cout<<DP[N-1][H]<<endl;
}



Measured memory_bytes: 42676
def solve(string):
    a, b, k = map(int, string.split())
    l = set(range(a, min(a + k, b)))
    r = set(range(max(a, b - k + 1), b + 1))
    return "\n".join(map(str, sorted(l | r)))


if __name__ == '__main__':
    print(solve(input()))


Measured memory_bytes: 3060
def main():
    S = list(input())
    lenS = len(S)-1

    ans = 0
    for i in range(2**lenS):
        Stmp = S.copy()
        jtmp = []
        for j in range(lenS):
            if (i>>j)&1:
                jtmp.append(j+1)
        for j in range(len(jtmp)):
            k = jtmp.pop()
            Stmp.insert(k, '+')
        listS = ''.join(Stmp).split('+')
        intS = [int(x) for x in listS]
        ans += sum(intS)

    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
// inputに入力データ全体が入る
function Main(input) {
  // まずメインの入力の値をとる
  var a = input.split("\n");
  // 500円
  const fh = parseInt(a[0],10);
  // 100円
  const h = parseInt(a[1],10);
  // 50円
  const ft = parseInt(a[2],10);
  // 金額の総量
  const amo = parseInt(a[3],10); 
  
  //最終的な答えの変数
  var count = 0;
  
  for(x = 0; x<= fh; x++){
    for(y = 0; y<= h; y++){
      for(z = 0; z <= ft; z++){
        if((50*z + 100*y + 500*x) == amo){
          count+=1;
        }
     }
    }
  }
  console.log(count);  
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 11468
N, A, B = map(int, input().split())

t = float('inf')
if abs(A - B) % 2 == 0:
    t = min(abs(A - B) // 2, t)
t = min((A - 1 + 1) + (B - A - 1) // 2, t)
t = min((N - B + 1) + (N - (A + (N - B + 1))) // 2, t)
print(t)

Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  long long k,a,b;
  cin >> k >> a >> b;
  long long num_c = 1;
  long long kane = 0;
  if(b - a > 2){
    while(k > 0){
      if(num_c >= a && k >= 2){
        num_c -= a;
        ++kane;
        --k;
        if(k == 0) break;
      }
      if(kane >= 1){
        num_c += b;
        --kane;
        --k;
        if(k == 0) break;
      }else{
        ++num_c;
        --k;
        if(k == 0) break;
      }
    }
  }else{
    while(k > 0){
      ++num_c;
      --k;
    }
  }
  cout << num_c << endl;
  return 0;
}

Measured memory_bytes: 256
class Node:
	def __init__(self, id):
		self.id = id
		self.parent_id = -1
		self.depth = 0
		self.children = None
	def get_type(self):
		if self.parent_id == -1:
			return 'root'
		elif self.children == None or len(self.children) == 0:
			return 'leaf'
		return 'internal node'
	def __str__(self):
		ret = 'node ' + str(self.id) + ': '
		ret += 'parent = ' + str(self.parent_id) + ', '
		ret += 'depth = ' + str(self.depth) + ', '
		ret += self.get_type() + ', '
		ret += '['
		for i in range(len(self.children)):
			ret += str(self.children[i])
			if i != len(self.children) - 1:
				ret += ', '
		ret += ']'
		return ret

n = int(input())
nodes = [Node(i) for i in range(n)]
for i in range(n):
	a = list(map(int, input().split()))
	id = a[0]
	node = nodes[id]
	if node.parent_id != -1:
		node.depth = nodes[node.parent_id].depth + 1

	m = a[1]
	children = [0] * m
	for j in range(m):
		child_id = a[j + 2]
		children[j] = child_id
		nodes[child_id].parent_id = id
		nodes[child_id].depth = node.depth + 1
	node.children = children

for i in range(n):
	print(nodes[i])



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

using namespace std;

int main()
{
    string a, b;
    cin >> a >> b;
    bool da=false;
    a=a+b[b.length()-1];
    if(a==b)
        cout << "Yes";
    else
        cout << "No";

    return 0;
}


Measured memory_bytes: 3592
package main

import (
	"bufio"
	"os"
	"strconv"
	"fmt"
)

var scanner = bufio.NewScanner(os.Stdin)

func nextInt() int {
	scanner.Scan()
	i, e := strconv.Atoi(scanner.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func binarySearch(target int, ints []int) bool {
	low := 0
	high := len(ints)-1
	for low <= high {
		mid := (low + high)/2
		guess := ints[mid]
		if guess == target {
			return true
		}
		if guess > target {
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	return false
}

func main() {
	scanner.Split(bufio.ScanWords)
	n := nextInt()
	a := make([]int, n)
	for i :=range a {
		a[i] = nextInt()
	}
	m := nextInt()
	b := make([]int, m)
	for i := range b {
		b[i] = nextInt()
	}
	flag := true
	for _, v := range b {
		if binarySearch(v, a) {
			continue
		} else {
			flag = false
			break
		}
	}
	if flag {
		fmt.Println(1)
	} else {
		fmt.Println(0)
	}
}


Measured memory_bytes: 6960
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>
#include <deque>
#include <complex>
#include <bitset>

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<long long, long long> pll;
typedef vector<pll> vpll;

typedef long double ld;
typedef vector<ld> vld;

typedef vector<bool> vb;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, n) for (ll i = 1; i <= (n); i++)
#define rrep(i, n) for (ll i = (n) - 1; i >= 0; i--)
#define rreps(i, n) for (ll i = (n); i >= 1; i--)
#define all(v) (v).begin(), (v).end()

template <class T> void chmin(T& a, T b) { a = min(a, b);}
template <class T> void chmax(T& a, T b) { a = max(a, b);}

constexpr int INF = 1 << 30;
constexpr ll INFL = 1LL << 60;
constexpr ll MOD = 1000000007;
constexpr ld EPS = 1e-12;
ld PI = acos(-1.0);

void solve() {
    ll r, c, k;
    cin >> r >> c >> k;
    vvll v(r, vll(c, 0));
    rep(i, k) {
        ll _r, _c, _v;
        cin >> _r >> _c >> _v;
        --_r, --_c;
        v[_r][_c] = _v;
    }
    vector<vvll> dp(r, vvll(c, vll(4, 0)));
    dp[0][0][0] = 0;
    if(v[0][0] != 0) dp[0][0][1] = v[0][0];
    for(int i = 0; i < r; ++i) {
        for(int j = 0; j < c; ++j) {
            for(int l = 0; l < 4; l++) {
                if(i > 0) {
                    chmax(dp[i][j][0], dp[i - 1][j][l]);
                    if(v[i][j] > 0) chmax(dp[i][j][1], dp[i-1][j][l] + v[i][j]);
//                    if(l < 3 && v[i-1][j] > 0) chmax(dp[i][j][l+1], dp[i-1][j][l] + v[i-1][j]);
                }
                if(j > 0) {
                    chmax(dp[i][j][l], dp[i][j - 1][l]);
                    if(l < 3 && v[i][j] > 0) chmax(dp[i][j][l+1], dp[i][j-1][l] + v[i][j]);
//                    if(v[i][j-1] > 0) chmax(dp[i][j][1], dp[i][j-1][l] + v[i][j-1]);
                }
            }
        }
    }
    ll ans = 0;
    rep(i, 4) chmax(ans, dp[r-1][c-1][i]);
    /*
    rep(i, 4) {
        rep(j, r) {
            rep(l, c) cout << dp[j][l][i] << ' ';
            cout << endl;
        }
        cout << endl;
    }
    */
    cout << ans << endl;
    return;
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}

Measured memory_bytes: 706592
#include<stdio.h>
#include<string.h>
int main()
{
    char a[2][3];
    int i,j;
    for(i=0;i<2;i++)
    {
        for(j=0;j<3;j++)
        {
            scanf("%c",&a[i][j]);
        }
        getchar();
    }
    for(i=0;i<2;i++)
    {
        for(j=0;j<3;j++)
        {
            if(a[i][j]!=a[1-i][2-j])
            {
                 printf("NO\n");
                  return 0;

            }

        }
    }
    printf("YES\n");
    return 0;

}


Measured memory_bytes: 128
char s[999][999];j;n;a[999];b[999];c;d;main(i){for(;~scanf("%s",s[n]);n++)for(j=0;s[n][j];b[j++]|=c)a[n]|=c=s[n][j]==35;for(;++i<n;d&&puts(""))for(d=0,j=-1;s[i][++j];c&&putchar(s[i][j]))d|=c=a[i]&b[j];}

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

const long long MX = 1e18;

void solve(long long N, std::vector<long long> A){
    unsigned long ans = 1;
    rep(i,N){
        if(A[i] == 0){
            cout << 0 << endl;
            return;
        }
    }
    rep(i,N){

        if(A[i] <= MX/ans){
            ans = ans * A[i];
        }else{
            cout << -1 << endl;
            return;
        }
        
    }


    cout << ans << endl;

}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    solve(N, A);
    return 0;
}


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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

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

using ll=long long;
using R=long double;
const R EPS=1e-9; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max<R>(x,0.0));}

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

// Problem Specific Parameter:

int main(void){
	string s;
	cin >> s;
	cout << s.substr(0,4) << " " << s.substr(4,8) << endl;
	return 0;
}

Measured memory_bytes: 256
lines = $stdin.read
array = lines.split("\n")

def knapsack(n,w,items)

  dp = Array.new(N+1).map{Array.new(W+1, 0)}

  for i in 1...N+1
    for w in 1...W+1
      if items[i].w <= w
        dp[i][w] = [items[i].v + dp[i][w - items[i].w], dp[i-1][w]].max
      else
        dp[i][w] = dp[i-1][w]
      end
    end
  end

  dp
end

Item  = Struct.new(:v, :w)
N,W   = array[0].split(" ").map(&:to_i)

items = [Item.new(0,0)]
array[1..array.length].each do |s|
  item = Item.new
  item.v, item.w = s.split(" ").map(&:to_i)
  items << item
end

dp = knapsack(N,W,items)
puts dp.max.max

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

const int Maxn = 1005;
string s;
bool vis[Maxn];
int cnt1[Maxn], n, cnt2[Maxn], ans;
int main()
{
	scanf("%d", &n);
	cin >> s;
	for (int i = 0; i < n; i++)
		cnt1[s[i] - '0']++;
	for (int i = 0; i < n; i++)
	{
		cnt1[s[i] - '0']--;
		for (int j = 0; j <= 9; j++)
			if (cnt2[j])
				for (int k = 0; k <= 9; k++)
					if (cnt1[k])
						vis[j * 100 + (s[i] - '0') * 10 + k] = true;
		cnt2[s[i] - '0']++;
	}
	for (int i = 0; i <= 999; i++)
		if (vis[i]) ans++;
	printf("%d", ans);
}

Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, [ $t:tt ]) => {{
        let len = read_value!($next, usize);
        (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    }};

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        k: i64,
        a: i64,
        b: i64,
    }
    let mut k = k;
    let mut tot = 1;
    let r = min(k, a - 1);
    tot += r;
    k -= r;
    if tot >= a {
        if b - a > 2 {
            tot += (k / 2) * (b - a) + (k % 2);
        } else {
            tot += k;
        }
    }
    puts!("{}\n", tot);
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


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

typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
int main() {
  char maze[1001][1001];
  int dx[4]={1,0,0,-1};
  int dy[4]={0,1,-1,0};
  queue<pint> que;
  int d[1001][1001];
  const int INF=2001;
  int h,w;
  cin >> h >> w;
  rep(i,h){
    rep(j,w){
      cin >> maze[i][j];
      d[i][j]=INF;
      if (maze[i][j]=='#'){
        pint s(i,j);
        que.push(s);
        d[i][j]=0;
      }
    }
  }
  while (!que.empty()){
    pint ss = que.front();
    que.pop();
    rep(i,4){
      int nx=ss.first+dx[i], ny=ss.second+dy[i];
      if(nx >= 0 && nx < h && ny >=0 && ny < w && d[nx][ny]==INF && maze[nx][ny]!='#'){
         pint m(nx,ny);
         d[nx][ny]=d[ss.first][ss.second]+1;
         que.push(m);
      }
    }
  }
  
 int ans=0;
 rep(i,h){
  rep(j,w){
      if (ans < d[i][j]) ans = d[i][j];
    }
  }
   
  cout << ans << endl;
  pint v=que.front();que.pop();
  
  //out << v.first  << ' ' << v.second << endl;
  
 
  return 0;
}

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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define LCM(a, b) (a) / __gcd((a), (b)) * (b)
#define CEIL(a, b) (a)/(b)+(((a)%(b))?1:0)
#define log_2(a) (log((a)) / log(2))
#define ln '\n'

using namespace std;
using LL = long long;
using ldouble = long double;
using P = pair<int, int>;
using LP = pair<LL, LL>;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1e9 + 7;
static const int SIZE = 200005;

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

vector<LL> Div(LL n) {
    vector<LL> ret;
    for(LL i = 1; i * i <= n; ++i) {
        if(n % i == 0) {
            ret.pb(i);
            if(i * i != n) ret.pb(n / i);
        }
    }
    sort(all(ret));
    return ret;
}

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

    int X;
    cin >> X;
    while(X > 1) {
        for(int i = 2; i < X; ++i) {
            int t = X;
            while(t % i == 0) {
                t /= i;
            }
            if(t == 1) {
                cout << X << endl;
                return 0;
            }
        }
        --X;
    }
    cout << X << endl;
    return 0;
}



Measured memory_bytes: 3620
#include <stdio.h>
int main(){

	int N;
	scanf("%d",&N);

	int M0=100000;
	int n;

	for(n=0;n<N;n++){
		M0=M0+0.05*M0;
		if(M0%1000)M0=M0-M0%1000 +1000;
	}

	printf("%d\n",M0);
	return 0;
}

Measured memory_bytes: 592
//header{{{
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
//#include<boost/multiprecision/cpp_int.hpp>
//#include<boost/math/common_factor_rt.hpp>
//#include<boost/multiprecision/cpp_dec_float.hpp>
  
using namespace std;
//using namespace boost;
//using namespace multiprecision;  

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define Fixed fixed << setprecision(12)
#define int int64_t
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9+7; 
constexpr int mod2 = 998244353;

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class A, class B> using umap = unordered_map<A,B>;
  
inline int square(int a){ return a * a;}
inline int updiv(int a,int b){ return (a + b - 1) / b; }

template <class A, class B> inline int Max(const A &a, const B &b){ return (a < b ? b : a); }
template <class A, class B> inline int Min(const A &a, const B &b){ return (a > b ? b : a); }

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


signed main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n, k;
    cin >> n >> k;

    vector<int> a(n);

    rep(i,n){
        cin >> a[i];
    }

    int x = -1;

    rep(i,k){
        vector<int> imos(n+1);
        rep(j,n){
            imos[max(int64_t(0), j - a[j])]++;
            imos[min(n, j + a[j] + 1)]--;
        }
        int minv = LINF, maxv = 0;
        rep(j,n){
            imos[j + 1] += imos[j];
            chmin(minv, imos[j]);
            chmax(maxv, imos[j]);
        }
        if(minv == maxv){
            x = i;
            break;
        }
        rep(j,n){
            a[j] = imos[j];
        }
    }

    if(x == -1){
        rep(i,n){
            cout << a[i] << (i == n-1 ? "\n" : " ");
        }
    }else{
        rep(i,n){
            cout << n << (i == n-1 ? "\n" : " ");
        }
    }

    return (0);
}


Measured memory_bytes: 6368
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <cctype>
#include <cstdlib>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <list>
#include<set>
#include<map>
using namespace std;
 
int main() {
	int L, R,m=2019*2019;
	cin >> L >> R;
	int l = L % 2019, r = R % 2019;
	if (R-L >= 2018) cout << 0 << endl;
	else {
		for (int i = 0; i < 2019; i++) {
			if (l<r && (i<l || i>r) || l>r && i<l && i>r) continue;
			for (int j = 0; j < 2019; j++) {
				if (l<r && (j<l || j>r) || l>r && j<l && j>r ||i==j) continue;
				m = min(m, i * j % 2019);
			}
		}
	cout << m << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#define ll long long
#define f(i, n) for (int i=0; i < n; i++)
// sort(bb, bb+n);
 
using namespace std;
int main()
{
    ll a,b,c;
    cin >> a >> b >> c;
    ll p = a/(b+c);
    ll m = a % (b+c);

    if(m < b){
        cout << p * b + m <<endl;
    }
    else {
        cout << p * b + b << endl; 
    }
   
    return 0;
}

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

using namespace std;

const int maxm = 1e6 + 5;

int a[maxm], mf[maxm];
unordered_map <int, int> ump;
bool not_pairwise = false;

void init() {
  mf[1] = 1;
  for(int i = 2; i < maxm; i += 2) {
    mf[i] = 2;
  }
  for(int i = 3; i < maxm; i += 2) {
    if(!mf[i]) {
      mf[i] = i;
      for(long long j = 1ll * i * i; j < maxm; j += i) {
        mf[j] = i;
      }
    }
  }
}

void factorize(int x) {
  vector<int> a;
  while(x > 1) {
    a.push_back(mf[x]);
    x /= mf[x];
  }
  for(int y : a) {
    if(ump[y] == 1) {
      not_pairwise = true;
    }
  }
  for(int y : a) {
    ump[y] = 1;
  }
}

int main() {
  init();
  int n;
  cin >> n;
  int g = -1;
  for(int i = 0; i < n; i++) {
    cin >> a[i];
    if(g == -1) g = a[i];
    else g = __gcd(g, a[i]);
    factorize(a[i]);
  }
  if(!not_pairwise) cout << "pairwise coprime";
  else if(g == 1) cout << "setwise coprime";
  else cout << "not coprime";
}

Measured memory_bytes: 14272
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<iterator>
//#include<math.h>

using namespace std;
#define int long long
/*                      */    //#undef int
#define INF 1000000009
#define INFL 1000000000000000018ll
#define mod 1000000007ll
#define pb push_back
#define fi first
#define se second
#define mk make_pair
typedef pair<int, int> PA;
typedef priority_queue<int> PQ;
typedef priority_queue<PA, vector<PA>, greater<PA> >PQG;

int n, a, b;

signed main()
{
    cin >> n;
    if(n == 2){
        cin >> a >> b;
        cout << a + b << endl;
    }
    else {
        cout << "Hello World" << endl;
    }



    return 0;
}
/*


*/



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
using namespace std;

int main()
{
	int N, M;
	cin >> N >> M;
	vector<pair<int, int>> list;
	for (auto i = 0; i < M; ++i)
	{
		int a, b;
		cin >> a >> b;
		list.push_back(make_pair(b, a));
	}
	sort(list.begin(), list.end());

	auto result = 0;
	auto current = 0;
	for (auto i = 0; i < M; ++i)
	{
		auto& p = list[i];
		if (p.second >= current)
		{
			++result;
			current = p.first;
		}
	}

	cout << result << endl;

	return 0;
}


Measured memory_bytes: 1400
#include<iostream>
#include<algorithm>
#include<numeric>
using namespace std;

int main(){
    int n, k, a;
    cin >> n >> k;

    int x[n];
    for(int i = 0; i < n; i++)  x[i] = 0;
    for(int i = 0; i < n; i++){
        cin >> a;
        x[a-1]++;
    }

    sort(x, x+n);
    reverse(x, x+n);

    cout << accumulate(x+k, x+n, 0) << endl;

    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{
    int H,W; cin>>H>>W;
    int ans;
    if(H%3==0 or W%3==0) ans=0;
    else{
        ans=min(H,W);
        REP(k,2){
            for(int i=1;i<=H-1;i++){
                int a=i*W;
                int b=(H-i)*(W/2);
                int c=(H-i)*(W-W/2);
                ans=min(ans,max(a,c)-min(a,b));
            }
            swap(H,W);
        }
    }
    cout<<ans<<endl;
}


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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define MAXN 1000010
#define rep(i,n) for (int i = 0; i < (n); ++i)
const ll mod = 1e9+7;

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

int main() {
    int n;
    int res;
    int max_count = -1;

    cin >> n;

    for(int i=1; i<=n; ++i) {

        int count = 0;
        int tmp = i;

        while(tmp%2 == 0) {
            tmp = tmp/2;
            ++count;
        }

        if (count > max_count) {
            max_count = count;
            res = i;
        }
    }

    cout << res  <<endl;
        
}



Measured memory_bytes: 256
N=int(input())
ab=[[0 for i in range(9)] for j in range(9)]
for i in range(1,N+1):
  if(i%10!=0):
    s=str(i)
    ab[int(s[0])-1][int(s[-1])-1]+=1
ans=0
for i in range(9):
  for j in range(9):
    ans+=ab[i][j]*ab[j][i]
print(ans)

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n,k; string s; cin>>n>>k>>s;
	vector<int>a(1,0);
	if(s.front()=='0')a.emplace_back(0);
	for(int i=0;i<s.size();){
		int cnt=0; char c=s.at(i);
		while(i<s.size()&&s.at(i)==c)++i,++cnt;
		a.emplace_back(cnt);
	}
	for(int i=1;i<a.size();++i)a.at(i)+=a.at(i-1);
	if(s.back()=='0')a.emplace_back(a.back());
	int ans=0;
	for(int i=0;i<a.size();i+=2){
		ans=max(ans,a.at(min(i+k*2+1,(int)a.size()-1))-a.at(i));
	}
	cout<<ans<<"\n"s;
}

Measured memory_bytes: 1020
h,w=map(int,input().split());w+=2
s=["."*w]+["."+input()+"." for _ in[0]*h]+["."*w]
for i in range(1,h+2):
	for j in range(1,w):
		if s[i][j]=="#":
			if "#" not in (s[i-1][j],s[i+1][j],s[i][j-1],s[i][j+1]):
				print("No");exit()
print("Yes")

Measured memory_bytes: 3064