akhauriyash/Code-Regression huggingface dataset:
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <cstdlib>
#define rep(i,n) for(int i = 0;i<(n);i++);
#define all(a) (a).begin(),(a).end()
using namespace std;
using ld = long double;
using ll = long long;
const ll INF = 100100100100100;
ll gcd(ll a,ll b) {//a>b
	if (a < b)swap(a, b);
	if (a % b == 0) return b;
	else return gcd(b, a % b);
}

int main() {
	ll N;
	cin >> N;
	map<ll, ll> num;
	ll n = 0;
	vector<ll> M;
	for (int i = 0; i < N; i++) {
		cin >> n;
		num[n]++;
		if (num[n] == 1) {
			M.push_back(n);
		}
	}
	ll ans = 0;
	for (int i = 0; i < M.size();i++) {
		if (num[M[i]] < M[i]) ans += num[M[i]];
		else if (num[M[i]] > M[i]) ans += num[M[i]] - M[i];/*4 3 3 3  -> 28*/
	}
	cout << ans << endl;
}

Measured memory_bytes: 7028
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pb push_back
#define ll long long int
#define w(t) int t;cin>>t; while(t--)
#define mp make_pair
#define int128 __int128_t
#define pii pair<int,int>
#define fi first
#define se second
#define fr(n) for(int i=0;i<n;i++)
#define rep(j,n) for(int i=j;i<n;i++)
#define um unordered_map
#define M 1000000009
#define pq priority_queue
#define pqm priority_queue <int, vector<int>, greater<int> >
int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n,k;
	cin>>n>>k;
	vi v(n);
	fr(n){
		cin>>v[i];
	}
	vi dp(n,INT_MAX);
	dp[0]=0;
	rep(1,n){
		for(int j=i-k;j<i;j++){
			if(j>=0){
				dp[i]=min(dp[i],dp[j]+abs(v[i]-v[j]));
				//cout<<dp[i]<<" "<<i<<" "<<j<<endl;
			}
		}		
	}
//	fr(n){
//		cout<<dp[i]<<" ";
//	}
	cout<<dp[n-1]<<"\n";
	return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
const int N=3e3+5;

int ma[N][N],cnt;

struct node
{
	int x,y;
}s[100000];

bool cmp(node a,node b)
{
	if(a.x!=b.x)
		return a.x<b.x;
	return a.y<b.y;
}

int main()
{
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
	{
		char c;
		cin>>c;
		if(c=='#')
		{
			s[++cnt].x=i;
			s[cnt].y=j;
		}
	}
	sort(s+1,s+1+k,cmp);
	int nl=1,nr=1;
	for(int i=1;i<=cnt;i++)
	{
		int l=s[i].y;
		int r=s[i].x;
		for(int ii=nr;ii<=r;ii++)
			for(int jj=nl;jj<=l;jj++)
				ma[ii][jj]=i;
		if(i==cnt||s[i+1].x!=s[i].x)
		{
			for(int ii=nr;ii<=r;ii++)
			for(int jj=s[i].y+1;jj<=m;jj++)
				ma[ii][jj]=i;
			nr=s[i].x+1;
			nl=1;
			continue;
		}
		nl=s[i].y+1;
	}
	for(int i=1;i<=n;i++)
	{
		if(!ma[i][1])
		{
			for(int j=1;j<=m;j++)
				ma[i][j]=ma[i-1][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			cout<<ma[i][j]<<' ';
		cout<<endl;
	}
    return 0;
}


Measured memory_bytes: 6144
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
       Scanner sc = new Scanner(System.in);
       int N = sc.nextInt();//与えれる整数
       int total = 0;
       String arrays[] = null;
       String kazu_string = String.valueOf(N);
       arrays =  kazu_string.split("");
       for(int i = 0; i < arrays.length; i++) {
            total += Integer.parseInt(arrays[i]);
        }
        if((N % total) == 0){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 22996
import math
a, b, x = map(float, input().split())
s = a * b * math.sin(math.radians(x)) / 2
l = a + b + math.sqrt(a * a + b * b - 2 * a * b * math.cos(math.radians(x)))
h = b * math.sin(math.radians(x))
print('%f' % s)
print('%f' % l)
print('%f' % h)


Measured memory_bytes: 5688
// Stack
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 200

void initialize();
int isEmpty();
int isFull();
void push(int);
int pop();


int top, S[1000];

int main(){
  int i, n, a, b;
  char str[100];
  initialize();
  top = 0;

  while(scanf("%s", str) != EOF){
    if(str[0] == '+'){
      a = pop();
      b = pop();
      push(a + b);
    }
    else if(str[0] == '-'){
      b = pop();
      a = pop();
      push(a - b);
    }
    else if(str[0] == '*'){
      a = pop();
      b = pop();
      push(a * b);
    }
    else{
      push(atoi(str));
    }
  }
  printf("%d\n", pop());
  
  return 0;
}

void initialize(){
  top = 0;
}

int isEmpty(){
  if(top == 0)return 1;
  else return 0;
}

int isFull(){
  if(top >= MAX - 1)return 1;
}

void push(int x){
  //if(isFull() == 1) exit(8);
  top++;
  S[top] = x;
}

int pop(){
  //if(isEmpty() == 1) exit(8);
  //else {
    top--;
    return S[top + 1];
    //}
}



Measured memory_bytes: 2108
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <string>

using namespace std;

int main() {
	int a, b;
	cin >> a >> b;
	int diff = b - a;
	int h = diff * (diff + 1) / 2;
	int ans = h - b;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <tuple>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

signed main() {
	int a, b;
	
	cin >> a >> b;
	if (a < b) swap(a, b);
	if ((a - b) % 2) cout << "IMPOSSIBLE" << endl;
	else cout << (a + b) / 2 << endl;
	return 0;
}

Measured memory_bytes: 256
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <iomanip>
#include <complex>
#include <bitset>
#include <stack>
 
using namespace std;
 
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define repl(i,s,n) for(int i=s; i<=n; ++i)
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define ktya(x) sort(all(x))
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 1e18
#define INFLL 1000000000000000007LL
#define SIZE 200105
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define mind(a,b) (a>b?b:a)
#define maxd(a,b) (a>b?a:b)

typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
typedef pair<int,ll> pill; typedef pair<ll,int> plli; 
typedef pair<double, int> pdi;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
typedef complex<double> P;
ll MOD = 1000000007;
//ll MOD=998244353;
typedef ll Weight;
struct Edge {
	int src, dst;
	Weight weight;
};
bool operator < (const Edge &e, const Edge &f) {
	return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
	e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
vi ones;
ll powMod(ll x, ll k, ll m) {//x^k (mod n)
	if (k == 0)     return 1;
	if (k % 2 == 0) return powMod(x*x % m, k/2, m);
	else            return x*powMod(x, k-1, m) % m;
}
ll pow23(ll k2, ll k3){
	return (powMod(2,k2,MOD)*powMod(3,k3,MOD))%MOD;
	
}
int main(){
	string str;
	cin>>str;
	int n=str.size();
	rep(i,n){
		if(str[i]=='1')ones.pb(i);
	}
	int m=ones.size();
	ll ans=0;
	ans+=pow23(0, n-1);
	rep(j,m-1){
		ans+=pow23(j+1,n-1-ones[j+1]);
		ans%=MOD;
	}
	ans+=pow23(m ,0);
	ans%=MOD;
	cout<<ans<<endl;
}

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    string X;
    ll ans = 0;
    ll st = 0;
    cin >> X;
    iter(c, X) {
        if(c == 'T') {
            if(st > 0) st--;
            else ans++;
        } else {
            st++;
        }
    }
    ans += st;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <math.h>
#include <cmath>
#include <limits>
#include <numeric>
#include <iomanip>
#include <stdio.h>
#define INF 1000000000
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
typedef long long int ll;
using namespace std;

int main() {

	ll n, a, b; cin >> n >> a >> b;
	ll ans = 0;
	ans += (n / (a + b)) * a;
	if (n % (a + b) <= a) { ans += n % (a + b); }
	else { ans += a; }
	cout << ans << endl;

	
	

	

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	string s; cin >> s;
	if(s=="abc"||s=="acb"||s=="bac"||s=="bca"||s=="cab"||s=="cba"){
		cout << "Yes" << endl;
		return 0;
	}
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int               long long
#define ff                first
#define ss                second
#define md                1000000007
#define md1               998244353
#define inf               1000000000000000
#define minf              -1000000000000000
#define pb                push_back
#define in                insert
#define mkp               make_pair
#define mpll              map<ll,ll>
#define len(p)            (ll)p.size()
#define pll               pair<ll,ll>
#define all(v)            v.begin(),v.end()
#define mem(a,t)          memset(a,t,sizeof(a))
#define endl              "\n"
#define ar                array
#define vl                vector<ll>
#define vpll              vector<pair<ll,ll>>
#define f(i,yha,wha)      for(ll i=yha;i<wha;i++)
#define rf(i,wha,yha)     for(ll i=wha;i>=yha;i--)
#define f0(n)             for(ll i=0;i<n;i++)
#define f1(n)             for(ll i=1;i<=n;i++)
#define fg(i,yha,wha,gap) for(ll i=yha;i<wha;i+=gap)


void flash()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}


void solve()
{
    ll x;
    cin >> x;

    ll val = 100;
    ll cnt = 0;
    while (val < x)
    {
        cnt++;
        val = val + val / 100;
    }
    cout << cnt << endl;




}

int32_t main()
{
    flash();
    int t;
    t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3636
void main() {
	auto ip = readAs!(int[]), A = ip[0], B = ip[1], C = ip[2];
	if(ip.sort().uniq.array.length == 2) writeln("Yes");
	else writeln("No");
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define rg register
using namespace std;
const int MAXN=2e5+10;
ll Ans,n,Seq[MAXN],Pre[MAXN],Odd[MAXN],Even[MAXN];
ll Dp[MAXN][4];
inline ll Min(rg ll A,rg ll B){   return A<B?A:B;   }
int main()
{   memset(Dp,0X7f,sizeof(Dp));
	scanf("%lld",&n),Dp[0][0]=0;
	for(rg int i=1;i<=n;i++) scanf("%lld",&Seq[i]),Ans+=Seq[i];
	for(rg int i=1;i<=n;i++) Odd[i]=(Seq[i]&1),Even[i]=(Seq[i]&&(~Seq[i]&1));
	for(rg int i=1;i<=n;i++)
	{	Dp[i][0]=Dp[i-1][0]+Seq[i];
		Dp[i][1]=Min(Dp[i-1][1],Dp[i-1][0])+(Seq[i]?!Even[i]:2);
		Dp[i][2]=Min(Dp[i-1][2],Min(Dp[i-1][1],Dp[i-1][0]))+(!Odd[i]);
		Dp[i][3]=Min(Dp[i-1][3],Min(Dp[i-1][2],Min(Dp[i-1][1],Dp[i-1][0])))+(Seq[i]?!Even[i]:2);
	}
	for(rg ll i=n,Sum=0;i>=1;i--) Ans=Min(Ans,Min(Dp[i][3],Dp[i][2])+Sum),Sum+=Seq[i];
	printf("%lld\n",Ans);
}


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

int N, cnt[100005];

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int x;
		scanf("%d", &x);
		cnt[x]++;
	}
	if (N % 2 == 0) {
		for (int i = 1; i < N; i += 2) {
			if (cnt[i] != 2) {
				printf("0\n");
				return 0;
			}
		}
	} else {
		if (cnt[0] != 1) {
			printf("0\n");
			return 0;
		}
		for (int i = 2; i < N; i += 2) {
			if (cnt[i] != 2) {
				printf("0\n");
				return 0;
			}
		}
	}
	N /= 2;
	int ans = 1;
	for (int i = 0; i < N; i++) {
		ans *= 2;
		ans %= 1000000007;
	}
	printf("%d\n", ans);
}


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

typedef long long ll;
#define rep(i,l,r) for(int i=l;i<=r;++i)
const int N=2e5+5;
char s[N];
deque<int>lk[26];
int n,c[N];

void add(int i,int w)
{
	for(;i;i-=i&-i)c[i]+=w;
}
int qiu(int i)
{
	int ans=0;
	for(;i<=n;i+=i&-i)ans+=c[i];
	return ans;
}

int main()
{
	//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
	scanf("%s",s+1);
	n=strlen(s+1);
	rep(i,1,n)lk[s[i]-'a'].push_back(i);
	int cnt=0;
	rep(i,0,25)
	if(lk[i].size()%2)++cnt;
	if(cnt>1){puts("-1");exit(0);}
	ll ans=0;
	int x=n+1;
	rep(i,0,25)
	if(lk[i].size()%2)
	{
		x=lk[i][lk[i].size()/2];
		rep(i,0,25)lk[i].clear();
		rep(i,1,n)if(i!=x)lk[s[i]-'a'].push_back(i);
	}
	rep(i,1,n)add(i,1);
	rep(i,1,n)
	if(i!=x)
	{
		int c=s[i]-'a';
		if(lk[c].empty())continue;
		if(i>x)++ans;
		add(lk[c].back(),-1);
		ans+=qiu(lk[c].back());
		lk[c].pop_front();
		lk[c].pop_back();
	}
	cout<<ans;
}

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

int main()
{


    int A, B, C;
    cin >> A >> B >> C;
    if ((A <= C && C <= B)|| (A >= C && C >= B)) {
        ce("Yes")

    }else {
        ce("No")
    }


}

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

int main(){
  int n, m, c = 0;
  cin >> n >> m;
  int A[n][m]{0};
  int B[m]{0};


  for(int i = 0; i < n; i++){
    for(int j = 0;j < m; j++){
    cin >> A[i][j];
    }
  }

  for(int i =0; i < m; i++){
    cin >> B[i];
  }

  for(int i = 0; i < n;i ++){
    for(int j = 0;j < m; j++){
      c += A[i][j] * B[j];
    }
    cout << c << endl;
    c = 0;
  }
  return 0;
}



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


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

    long long i,j,k,l,m,n,o,p;
    while(cin>>n)
    {
        n%=1000;
        if(n!=0)n=1000-n;
        cout<<n<<endl;
    }

    return 0;


}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define  pb push_back
#define nl "\n"
#define fastScan ios_base::sync_with_stdio(0); cin.tie(NULL);
#define int long long int
using namespace std;
int wt[123456];
int v[123456];
int dp[105][123456];
signed main()
{
	fastScan;
	int n,w;cin>>n>>w;
	for(int i=0;i<n;i++)
		cin>>wt[i]>>v[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=w;j++)
		{
			if(j>=wt[i-1])
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-wt[i-1]]+v[i-1]);
			else
				dp[i][j]=dp[i-1][j];
		}
	}
	cout<<dp[n][w]<<nl;
}


Measured memory_bytes: 99456
# B問題
N, M = map(int, input().split())
ab = []
for i in range(M):
    ab.append(list(map(int, input().split())))
ans = []
for i in range(N):
    tmp = 0
    for k in range(M):
        if i+1 in ab[k]:
            tmp += 1
    ans.append(tmp)
for i in range(N):
    print(ans[i])

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

int main() {
	int a, b;
	int cnt = 0;
	cin >> a >> b;
	for (int i = a; i < b + 1; i++)
	{
		if (i / 1000 == i % 10 * 10 + i / 10 % 10) cnt++;
	}
	cout << cnt << endl;
}

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

int main() {
	int n; cin >> n;
	vector<pair<int, int>>AB(n);
	for (auto&& x : AB) {
		int a, b; cin >> a >> b;
		x.first = a, x.second = b;
	}

	long long ans = 0;
	for (int i = n - 1; i >= 0; i--) {
		if ((AB[i].first + ans) % AB[i].second == 0)continue;
		else{
			ans += (AB[i].second) - (AB[i].first + ans) % AB[i].second;
		}
	}
	cout << ans << endl;

	return 0;
}

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

typedef long long ll;
const int MAX_N = 300030;
int par[MAX_N];
int rnk[MAX_N];
int n;

void init(){
  for (int i=0; i<n; i++){
    par[i] = i;
    rnk[i] = 0;
  }
}

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

void unite(int x, int y){
  x = find(x);
  y = find(y);
  if (x==y) return;
  if (rnk[x]<rnk[y]){
    par[x] = y;
  } else {
    par[y] = x;
    if (rnk[x]==rnk[y]) rnk[x]++;
  }
}

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


int main(){
  cin >> n;
  init();
  vector<vector<ll>> x(n, vector<ll>(2)), y(n, vector<ll>(2));
  for (int i=0; i<n; i++){
    cin >> x[i][0] >> y[i][0];
    x[i][1] = i; y[i][1] = i;
  }
  sort(x.begin(), x.end(), [](const auto& a, const auto& b){return a[0]<b[0];});
  sort(y.begin(), y.end(), [](const auto& a, const auto& b){return a[0]<b[0];});
  vector<vector<ll>> road;
  for (int i=0; i<n-1; i++){
    road.push_back({x[i+1][0]-x[i][0],x[i][1],x[i+1][1]});
    road.push_back({y[i+1][0]-y[i][0],y[i][1],y[i+1][1]});
  }
  sort(road.begin(), road.end(), [](const auto& a, const auto& b){ return a[0]<b[0]; });
  ll cost = 0;
  ll use = 0;
  for (int i=0;;i++){
    if (use==n-1) break;
    if (!same(road[i][1], road[i][2])){
      use++;
      cost += road[i][0];
      unite(road[i][1], road[i][2]);
    }
  }
  cout << cost << endl;
}


Measured memory_bytes: 24112
from sys import exit
N = int(input())
posx = 0
posy = 0
now = 0
for _ in range(N):
    t, x, y = map(int, input().split())
    time_elapsed = t - now
    now = t
    if abs(posx - x) + abs(posy - y) <= time_elapsed and time_elapsed % 2 == (abs(posx - x) + abs(posy - y)) % 2:
        posx = x
        posy = y
    else:
        print("No")
        exit()
print("Yes")


Measured memory_bytes: 45928
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 1e6 + 5;
int vis[maxn], prime[maxn], notPrime[maxn], num[maxn];
int total, n, maxx = 0, ans = 0, tmp;
void getPrime(int sum) {
    for (int i = 2; i <= sum; i++) {
        if (!notPrime[i]) {
            prime[++total] = i;
        }
        for (int j = 1; prime[j] * i <= sum; j++) {
            notPrime[i * prime[j]] = prime[j];
            if (i % prime[j] == 0)
                break;
        }
    }
}

void getInit() {
    memset(vis, 0, sizeof(vis));
    memset(notPrime, 0, sizeof(notPrime));
    memset(vis, 0, sizeof(vis));
}

int main() {
    getInit();
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &num[i]);
        maxx = max(maxx, num[i]);
    }
    getPrime(maxx);
    for (int i = 1; i <= n; i++) {
        while (notPrime[num[i]]) {
            tmp = notPrime[num[i]];
            vis[tmp]++;
            ans = max(ans, vis[tmp]);
            while (num[i] % tmp == 0)
                num[i] /= tmp;
        }
        if (num[i] != 1) {
            vis[num[i]]++;
            ans = max(ans, vis[num[i]]);
        }
    }
    if (ans <= 1)
        printf("pairwise coprime\n");
    else if (ans < n)
        printf("setwise coprime\n");
    else
        printf("not coprime\n");
    getchar();
    getchar();
    return 0;
}


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

int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n), c(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    for (int i = 0; i < n; i++) cin >> c[i];
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ll p = lower_bound(a.begin(), a.end(), b[i]) - a.begin();
        ll q = c.end() - upper_bound(c.begin(), c.end(), b[i]);
        ans += p * q;
    }
    cout << ans << endl;
}


Measured memory_bytes: 1408
#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> >;
typedef pair<int, int> P;
typedef int64_t ll;
const int MAX_N = 10000;
const int INF = 1000000000;


int main() {
	int N, K;
	cin >> N >> K;
	vector<int> X(N);
	int ans = 0;
	rep(i, N) {
		cin >> X.at(i);
		if (X.at(i) > K-X.at(i)) {
			ans += (K-X.at(i)) * 2;
		}
		else {
			ans += X.at(i) * 2;
		}
	}
	cout << ans << endl;
}

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

int main() {
  int n,k;
  cin>>n>>k;
  if(n%k==0) {
    cout <<"0"<<endl;
  } else {
    cout<<"1"<<endl;
  }
  return 0;
}


Measured memory_bytes: 764
#include <iostream>

using namespace std;

int main() {
	int N;
	int two = 0, four = 0;

	cin >> N;
	for(int i = 0; i < N; i++) {
		int a;
		cin >> a;
		if(a % 4 == 2) two++;
		if(a % 4 == 0) four++;
	}
	
	int odd = N - two - four;
	if(two > 0) odd++;

	if(odd <= four + 1) cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll INF = 1'010'000'000'000'000'017LL;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()

int main() {
    // AtCoder
    // template
    ll h, w;
    cin >> h >> w;
    vector<string> a(h);
    rep(i, h) { cin >> a.at(i); }

    vector<bool> resh(h, false);
    vector<bool> resw(w, false);
    rep(i, h) {
        rep(j, w) {
            if(a.at(i).at(j) == '#') {
                resh.at(i) = true;
                resw.at(j) = true;
            }
        }
    }

    rep(i, h) {
        if(resh.at(i)) {
            rep(j, w) {
                if(resw.at(j)) {
                    cout << a.at(i).at(j);
                }
            }
            cout << endl;
        }
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string s,t;
  cin >> s >> t;
  int count = 0;
  
  for(int i = 0; i < s.size(); i++){
    if(s.at(i) != t.at(i)){
      s.at(i) = t.at(i);
      count++;
    }
    else{
      continue;
    }
  }
  cout << count;
}


Measured memory_bytes: 3916
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0);
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl '\n'

const int M = 1e9+7;

using namespace std;

main()
{
    fast;
    int x;
    cin>>x;
    if (x<1200)
        cout<<"ABC\n";
    else
        cout<<"ARC\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define N 1000000007
typedef long long ll;
#define all(v) (v).begin(),(v).end()
#define sz(x) int(x.size())
int main(){
	string s;
	cin>>s;
	int k;
	cin>>k;
	int q=0;
	rep(i,sz(s)-1){
		if(s.at(i)==s.at(i+1)){
			q++;
			i++;
		}
	}
	string t;
	t=s+s;
	int p=0;
	rep(i,sz(t)-1){
		if(t.at(i)==t.at(i+1)){
			p++;
			i++;
		}
	}
	ll ans=0;
	if(k%2==0){
	ans=(p-q);
	ans*=(k-1);
	ans+=q;
	}else{
		ans=p;
		ans*=(k/2);
		ans+=q;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
n,k = map(int,input().split())
S = list(input())
if(S[k-1]=="A"):
  S[k-1]="a"
elif(S[k-1]=="B"):
  S[k-1]="b"
else:
  S[k-1]="c"
for i in range(n):
  print(S[i],end='')

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

bool highest(int a, vector<int>& h, vector<vector<int>>& e) {
	for (int c : e[a]) {
		if (h[a] <= h[c]) {
			return false;
		}
	}
	return true;
}

int main() {
	int n, m; cin >> n >> m;
	vector<int> h(n+1);
	for (int i=1; i<=n; i++) {
		cin >> h[i];
	}
	vector<vector<int>> e(n+1, vector<int>());
	for (int i=0; i<m; i++) {
		int a, b;
		cin >> a >> b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	int cnt = 0;
	for (int i=1; i<=n; i++) {
		cnt += highest(i, h, e);
	}
	cout << cnt;
}


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

int main(){
  int A;
  int64_t B;
  int64_t N;
  cin >> A >> B >> N;
  
  int64_t tisa = (N/B)*B-1;
  if(tisa<0){
    tisa = N;
  }
  
  cout << A*tisa/B - A*(tisa/B) << endl;
}


Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+3;
int a[N],d[N];
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t,i,j,n,m,l,r;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    d[1]=abs(a[1]-a[0]);
    for(i=2;i<n;i++)
    {
        l=abs(a[i]-a[i-1])+d[i-1];
        r=abs(a[i]-a[i-2])+d[i-2];
        d[i]=min(l,r);
    }
    cout<<d[n-1]<<"\n";
    return 0;
}

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

int dp[102][100005];

 main()
{

//		#ifndef ONLINE_JUDGE
//			freopen("input", "r", stdin);
//			freopen("output","w",stdout);
//	#endif


	int n,W;	cin>>n>>W;
	int v[n+1], w[n+1];

	for(int i=0;i<n;++i)	cin>>w[i]>>v[i];


	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=W;++j)
		{
			dp[i][j] = max( dp[i-1][j], (j - w[i-1]>=0 ? v[i-1] + dp[i-1][j-w[i-1]] : 0)); 
		}
	}

	// for(int i=1;i<=n;++i)
	// 	for(int j=1;j<=W;++j)
	// 		cout<<dp[i][j]<<" \n"[j==W];

	cout<<dp[n][W]<<endl;
}

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

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)



int main() {
    int n; cin >> n;
    string tmp;
    map<string, int> ma;
    rep(i, n) {
        cin >> tmp;
        ma[tmp]++;
    }
    int m; cin >> m;
    rep(i, m) {
        cin >> tmp;
        ma[tmp]--;
    }

    int ans = 0;
    for(auto itr : ma) {
        ans = max(itr.second, ans);
    }

    cout << ans << endl;

    return 0;
    
}


Measured memory_bytes: 256
// include
// ------------------------------------------------
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

// func
// ------------------------------------------------
int CalcSumOfDigit(int n);      // 各桁の和を計算する。
int getDigit(int n);            // 数字の桁数を取得する。
string upper(string str);       // 英字を大文字に変換する。
string lower(string str);       // 英字を小文字に変換する。

// define
// ------------------------------------------------
#define all(a)        (a).begin(),(a).end()
#define rall(a)       (a).rbegin(),(a).rend()
#define sz(a)         int((a).size())
#define rep(i,n)      for(int(i)=0;(i)<(n);(i)++)
#define repe(i,n)     for(int(i)=0;(i)<=(n);(i)++)
#define vsort(v)      sort((v).begin(),(v).end())
#define rvsort(v)     sort(rall((v)))
#define vi            vector<int>
#define GCD(a,b)      __gcd((a),(b))
#define LCM(a,b)      (a)/GCD((a),(b))*(b)
#define kiriage(a,b)  ((a)+(b)-1)/(b)

const int INF = 1e9;

typedef long long ll;
typedef unsigned long long ull;

// code
// ------------------------------------------------
int main() {

  ll n;cin >> n;
  vector<vector<ll>> G(n);

  for(int i =2 ;i <= n;i++)
  {
    ll a;
    cin >> a;
    G[a-1].push_back(i-1);
  }

  rep(i,n)
  {
    cout << sz(G[i]) << endl;
  }

  return 0;
}
// funcの実体
// ------------------------------------------------
int getDigit(int n)
{
  int i = 1;
  while(1)
  {
    n = n / 10;
    if(n == 1)
      break;
    i++;
  }
  return i;
}
int CalcSumOfDigit(int n)
{
  int s = 0;
  while(n)
  {
    s += n % 10;
    n = n / 10;
  }
  return s;
}

string upper(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(97 <= *itr && *itr <= 122)
    {
      *itr = *itr - 32;
    }
  }
  return str;
}

string lower(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(65 <= *itr && *itr <= 90)
    {
      *itr = *itr + 32;
    }
  }
  return str;
}


Measured memory_bytes: 14028
#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> d(n);

  for(int i=0; i<n; i++) {
    cin >> d[i];
  }
  sort(d.begin(),d.end());
  cout << d[n/2] - d[n/2-1] << endl;
}

Measured memory_bytes: 768
#include <functional>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <iomanip>
#include <utility>
#include <cstdlib>
#include <sstream>
#include <bitset>
#include <vector>
#include <cstdio>
#include <ctime>
#include <queue>
#include <deque>
#include <cmath>
#include <stack>
#include <list>
#include <map>
#include <set>

using namespace std;

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

#define dump(x)  cerr << #x << " = " << (x) << endl
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back

bool isLeep(int n){
    if((n%4==0 && n%100!=0) || n%400==0){
        return true;
    }
    else return false;
}


int main() {
    int a,b;
    bool flag=false;
    while(cin>>a>>b){
        if(a==0 && b==0)break;
        if(flag)cout<<endl;
        flag=true;
        
        int c=0;
        for(int i=a;i<=b;i++){
            if(isLeep(i)){
                c++;
                cout<<i<<endl;
            }
        }
        if(c==0)cout<<"NA"<<endl;
    }
    
    return 0;
}

Measured memory_bytes: 1160
def get_i() #空白区切の入力を数値(整数)の配列で返す
  return gets.chomp.split(" ").map(&:to_i)
end
def get_f() #空白区切の入力を数値(実数)の配列で返す
  return gets.chomp.split(" ").map(&:to_f)
end
def get() #空白区切の入力を文字列の配列で返す
  return gets.chomp.split(" ")
end
def get_nsp() #入力されたものを一文字ずつに区切った文字列の配列で返す
  return gets.chomp.split("")
end
def yn_judge(bool,y="Yes",n="No") #boolに真偽を投げることで、trueならy、falseならnの値を出力する
  return bool ? y : n 
end
def array(size1,init=nil,size2=1) #size2に二次元配列時の最初の要素数、size1に次の配列の大きさ、initに初期値を投げることでその配列を返す
  if size2==1
    return Array.new(size1){init}
  else
    return Array.new(size2){Array.new(size1){init}}
  end
end

N=gets.to_i
puts (N-1)*N/2

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

bool kaibun(int num){
  char S[10];
  string str, str1, str2;
  sprintf(S, "%d", num);
  str = S;
  str1=str.substr(0, str.length()/2);

  if(str.length()%2==0) str2=str.substr(str.length()/2);
  else str2=str.substr(str.length()/2+1);

  reverse(str2.begin(),str2.end());

  return str1 == str2;
}

int main()
{
  int A, B;
  int res = 0;
  cin >> A >> B;

  for(int i=A; i<=B; i++){
    if(kaibun(i)) {
      //cout << i << endl;                                                      
      res++;
    }
  }

  cout << res << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const ll INF = 1e9 + 7;
const ll inf = 1LL << 50;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////
int a[200100];
int b[200100];
int main() {
	int N; cin >> N;
	bool ok = true;
	NREP(i, N)cin >> a[i];
	for (int i = N / 2 + 1; i <= N; ++i) {
		b[i] = a[i];
	}
	for (int i = N / 2; i >= 1; --i) {
		int cnt = 0;
		for (int j = 2; i*j <= N; ++j) {
			if (b[i*j] == 1) {
				cnt++;
			}
		}
		b[i] = (a[i] + cnt) % 2;
	}
	int ans = 0;
	NREP(i, N) {
		if (b[i])ans++;
	}
	cout << ans << endl;
	for (int i = 1; i <= N; ++i) {
		if (b[i]) {
			cout << i << " ";
		}
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 2432
#include <stdio.h>

int main(void) {
  int h, w, i, j;
  while (1) {
    scanf(" %d %d", &h, &w);
    if (h == 0 && w == 0)
      return 0;
    for (i = 0; i < h; i++) {
      for (j = 0; j < w; j++) {
	printf("#");
      }
      printf("\n");
    }
    printf("\n");
  }
  return 0;
}



Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b,c,q=0;
	cin>>a>>b>>c;
	if(a+b==c)
	q=1;
	if(b+c==a)
	q=1;
	if(a+c==b)
	q=1;
	if(q)
	cout<<"Yes";
	else
	cout<<"No";
	
	
	
}

Measured memory_bytes: 256
import itertools
N,M = list(map(int,input().split()))
lis = []
for i in range(N):
    lis.append([i+1])
for i in range(M):
    a,b = list(map(int,input().split()))
    lis[a-1].append(b)
    lis[b-1].append(a)
pemls = [i for i in range(2,N+1)]
lis_root = list(itertools.permutations(pemls,N-1))

counter = 0
for i in range(len(lis_root)):
    now = 1
    step = [1]
    flag = 1
    for j in range(len(lis_root[i])):
        #print("root:"+str(lis_root[i])+ " now:"+str(now) )
        if lis_root[i][j] in lis[now-1]:
            now = lis_root[i][j]
            step.append(now)
        else:
            flag = 0
            break
        if len(step) == N:
            break
    if flag ==1:
        counter += 1
        #print(counter)
print(counter)


Measured memory_bytes: 9240
program probB
  implicit none
  integer n
  integer i,j,k,alice,bob
  integer,allocatable :: a(:),a_tmp(:)
  

  read(*,*) n
  allocate(a(n),a_tmp(n))
  read(*,*) a(1:n)

  a_tmp=a
  call quicksort(a_tmp,1,n)

  do i=1,n
     a(i)=a_tmp(n+1-i)
  end do

  alice=0
  bob=0

  do i=n,1,-1
     if(mod(i,2)==1) then
        alice=alice+a(i)
     else
        bob=bob+a(i)
     end if
  end do
  
  write(*,*) alice-bob
  
   
end program probB


recursive subroutine quicksort(a, first, last)
  implicit none
  integer a(*)
  integer first, last
  integer i, j
  integer x, t

  x = a( (first+last) / 2 )
  i = first
  j = last
  do
     do while (a(i) < x)
        i=i+1
     end do
     do while (x < a(j))
        j=j-1
     end do
     if (i >= j) exit
     t = a(i);  a(i) = a(j);  a(j) = t
     i=i+1
     j=j-1
  end do
  if (first < i - 1) call quicksort(a, first, i - 1)
  if (j + 1 < last)  call quicksort(a, j + 1, last)
end subroutine quicksort

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<long>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using vvl = vector<vector<long>>;
using pii = pair<int, int>;
using pil = pair<int, long>;
using pll = pair<long, long>;
using vc = vector<char>;
#define fix20 cout << fixed << setprecision(20)
#define YES cout << "Yes" << endl
#define NO cout << "No" << endl
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,s,t) for(int i=s; i<t; i++)
#define RNG(i,s,t,u) for(int i=s; i<t; i+=u)
#define MOD 1000000007
#define all(vec) vec.begin(), vec.end()

int main(){
  string s;
  cin >> s;
  int n = s.size();
  vi num(n);
  rep(i,n) num[i] = (s[i] - '0');
  vvl dp(2,vl(n));
  
  dp[0][n-1] = num[n-1];
  dp[1][n-1] = 10 - num[n-1];

  for(int i=n-2;i>=0;i--){
    dp[0][i] = min(dp[0][i+1] + num[i], dp[1][i+1] + num[i] + 1);
    dp[1][i] = min(dp[0][i+1] + 10 - num[i], dp[1][i+1] + 10 - (num[i] + 1));
  }
  cout << min(dp[0][0], dp[1][0] + 1) << endl;
}

Measured memory_bytes: 28676
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
#define ALL(a)  (a).begin(),(a).end()
const ll INF = 1e18+18;
const ll MAX = 200000;
const ll MOD = 1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;



int main(){
    ll N;
    cin>>N;
    ll Sum=0;
    rep(i, N){
        ll K=i+1;
        if(K%3&&K%5)Sum+=K;
    }
    cout<<Sum<<endl;
    return 0;
}



Measured memory_bytes: 3632
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <climits>
#include <cassert>
#include <algorithm>
#include <utility>

using namespace std;
using Int = long long int;
using UInt = unsigned long long int;
using VI = vector<long long int>;
using VVI = vector<vector<long long int> >;

int main(void) {
    Int n, k;
    cin >> n >> k;
    Int cnt = k;
    for (Int i = 1; i < n; ++i) {
        cnt *= (k - 1);
    }
    cout << cnt << endl;
    return 0;
}



Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
  ll N,K,X,Y;
  cin>>N;
  cin>>K;
  cin>>X;
  cin>>Y;
  if(N<=K) cout<<X*N<<endl;
  else cout<<(X*K)+((N-K)*Y)<<endl;
  return 0;
}
	


Measured memory_bytes: 256
import java.util.*;

public class Main {

    static int N;
    static int[] a;
    static long INF = Long.MAX_VALUE;
    static long[] ruiseki;
    static long[][] dp;

    static long dp(int left, int right) {
        if (dp[left][right]!=-1) return dp[left][right];
        if (left==right) {
            dp[left][right] = 0;
            return 0;
        }

        long min = INF;
        for (int i=left;i<right;i++) {
            min = Math.min(min, dp(left, i)+dp(i+1, right)+ruiseki[right+1]-ruiseki[left]);
        }
        dp[left][right] = min;
        return min;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = Integer.parseInt(sc.next());
        a = new int[N];
        ruiseki = new long[N+1];
        dp = new long[N][N];
        for (int i=0;i<N;i++) {
            for (int j=0;j<N;j++) {
                dp[i][j] = -1;
            }
        }
        for (int i=0;i<N;i++) {
            a[i] = Integer.parseInt(sc.next());
            ruiseki[i+1]=ruiseki[i]+a[i];
        }
        System.out.println(dp(0, N-1));
    }
}

Measured memory_bytes: 26552
#!/usr/bin/env python3
from functools import reduce

x, y = map(int, input().split())

mod = 10**9 + 7


def cmb(n, r, m):
    def mul(a, b):
        return a * b % m

    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return (over * pow(under, m - 2, m))%m


r = abs(x - y)
l = (min(x, y) - r) // 3
r += l
if l*2+r*1 in (x,y) and l >= 0:
    print(cmb(r + l, l, mod))
else:
    print(0)


Measured memory_bytes: 9556
N = int(input())
S = input()

# 西端の人がリーダーの場合
temp = 0
for j in range(1, N):
    temp += (S[j] == 'E')
    ans = temp

for i in range(1, N): # 西からi番目の人がリーダーの場合
    temp -= (S[i] == 'E')
    temp += (S[i - 1] == 'W')
    ans = min(ans, temp)

print(ans)

Measured memory_bytes: 9704
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll/*, vl, greater<ll>*/> pql; //降順(/*昇順*/)
typedef set<ll> sl;
typedef pair<ll, ll> pl;
typedef vector<vl> vvl;
typedef vector<pl> vpl;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, n) for(ll i = 1; i <= ll(n); i++)
//#define rep(i, k, n) for(ll i = k-1; i < ll(n); i++)
//#define rep2(i, k, n) for(ll i = k; i <= ll(n); i++)
#define all(v) (v).begin(), (v).end()
bool chmin(ll &a, ll b) {if(b < a) {a = b; return 1;} return 0;}
bool chmax(ll &a, ll b) {if(b > a) {a = b; return 1;} return 0;}
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const ll MAX = 1e9;
const char newl = '\n';

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

  ll n, k;
  string s;
  cin >> n >> k >> s;
  s[k-1] += 'a'-'A';
  cout << s << newl;
}

Measured memory_bytes: 3592
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>
#include <cmath>
#include <cassert>
#include <bitset>
#include <stack>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define int long long // at least int64 > 9*10^18
#define EL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
using Graph = std::vector<std::vector<int> >;
const int INF = 1e17;
/* libraries */

signed main() {
	std::string s,t;
	std::cin >> s >> t;
	if(t.substr(0,s.size())==s) print("Yes");
	else print("No");
	return 0;
}


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

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using vint = vector<int>;
using vll = vector<ll>;
using uint = unsigned int;
using ull = unsigned long long;

template<typename T> using uset = unordered_set<T>;
template<typename T1, typename T2> using umap = unordered_map<T1, T2>;

constexpr int INF = (1 << 30) - 1;
constexpr ll LLINF = 1LL << 60;
constexpr int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr char el = '\n';
constexpr int mod = 1000000007;

template<typename T> T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); }
template<typename T> T lcm(T a, T b) { return (a / gcd(a, b) * b); }
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

template<typename T>
ostream& operator <<(ostream &os, vector<T> &v) {
        for (auto &u : v) os << u << endl;
        return (os);
}

template<typename T>
istream& operator >>(istream &is, pair<vector<T>&, int> v) {
        while (v.second--) {
                T a;
                v.first.push_back(is >> a, a);
        }
        return (is);
}

template<typename T>
istream& operator >>(istream &is, vector<T> &v) {
        for (auto &u : v) is >> u;
        return (is);
}

int main() {
    ll H, W, h, w;
    ll big = 1000000000;
    cin >> H >> W >> h >> w;
    vector<vll> dat(H, vll(W, 0));
    
    for (int i = 0; i < H; i += h) {
        for (int j = 0; j < W; j += w) {
            dat[i][j] = big - 1;
        }
    }
    for (int i = h - 1; i < H; i += h) {
        for (int j = w - 1; j < W; j += w) {
            dat[i][j] = -big;
        }
    }

    ll sum = 0;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            sum += dat[i][j];
        }
    }

    if (sum <= 0) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
        for (int i = 0; i < H; i++) {
            cout << dat[i][0];
            for (int j = 1; j < W; j++) cout << " " << dat[i][j];
            cout << el;
        }
    }

    return (0);
}


Measured memory_bytes: 4864
n=int(input())
a=[0 for i  in range(10**5)]
for i in range(1,101):
  for j in range(1,101):
    for k in range(1,101):
      f=i**2+j**2+k**2+i*j+j*k+k*i
      a[f-1]+=1
for i in range(n):
  print(a[i])
      

Measured memory_bytes: 9988
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define cool ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) 
#define ll long long
#define MAX 1000001
int prime_no[MAX];
int g=0; 
void SieveOfEratosthenes(int n) 
{ 
    bool prime[MAX]; 
    memset(prime, true, sizeof(prime)); 
    for (int p=2; p*p<=n; p++){ 
        if (prime[p] == true){ 
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
    for (int p=2; p<=n; p++){
        if (prime[p]) {
       		prime_no[g]=p;
       		g++;
	   }	
	} 
}
void solve(){
	ll int n,k;
	cin>>n>>k;
	ll int a[n];
	for(int i=0;i<n;i++)
	cin>>a[i];
	ll int b[n];
	for(int i=0;i<n;i++)
	b[i]=10e9;
	b[0]=a[0];
	b[1]=abs(a[1]-a[0]);
	for(int i=2;i<n;i++){
		for(int j=1;j<=k;j++){
			if((i-j)!=0){
				b[i]=min(b[i],(abs(a[i]-a[i-j])+b[i-j]));
			}
			else if((i-j)==0){
				b[i]=min(b[i],(abs(a[i]-a[i-j])));
			}
		}
	}
	cout<<b[n-1];	
} 
int main()
{ 
    cool;
    int t;
    //cin>>t;
    t=1;
    while(t--){
    	solve();
	}
    return 0;
}


Measured memory_bytes: 1792