akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define RFOR(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define rep(i,n) FOR(i,0,(n))
#define REPS(i,n) FOR(i,1,(n)+1)
#define RREP(i,n) RFOR(i,0,(n))
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define debug(x) cout << #x << " = " << (x) << endl;
#define SORT(x) sort(rng(x))
#define RSORT(x) sort(rrng(x))
#define SUM(x) accumulate(rng(x),0)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int mod = 1000000007;
const double EPS = 1e-9;
const int INF = (1<<30)-1;
const ll INFLL = (1LL<<62)-1;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//cout << fixed << setprecision(10);

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

ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

// s = "LRRLRLRRLRLLR" -> t = "LRLRLRLRLR"
string str_uni(string s) {
  string ret;
  char d;
  int i = 0;
  while (i < s.size()) {
    d = s[i];
    int j = i;
    while (s[j] == d) {
      j++;
    }
    ret += d;
    i = j;
  }
  return ret;
}

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

  string t = str_uni(s);
  cout << sz(t) << endl;

  return 0;
}

Measured memory_bytes: 640
import std.range;
import std.conv;
import std.string;
import std.algorithm;
import std.array;
import std.stdio;

void main() {
	int n, k;
	readf("%s %s\n", &n, &k);

	auto ps = readln.chomp.split(' ').map!(to!uint).array;
	assert(k <= ps.length);
	
	ps.sort;

	ps.take(k).reduce!"a + b".writeln;
}


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

using namespace std;

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

  int n;
  cin >> n;
  n %= 10;

  if (n == 3) {
    cout << "bon" << '\n';
  } else if (n == 0 || n == 1 || n == 6 || n == 8) {
    cout << "pon" << '\n';
  } else {
    cout << "hon" << '\n';
  }

  return 0;
}


Measured memory_bytes: 3688
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int n = Integer.parseInt(sa[0]);
		double[] p = new double[n];
		sa = br.readLine().split(" ");
		for (int i = 0; i < n; i++) {
			p[i] = Double.parseDouble(sa[i]);
		}
		br.close();

		double[][] dp = new double[n + 1][n + 1];
		dp[0][0] = 1;
		for (int i = 1; i <= n; i++) {
			double pi = p[i - 1];
			dp[i][0] = dp[i - 1][0] * (1 - pi);
			for (int j = 1; j <= i; j++) {
				dp[i][j] = dp[i - 1][j - 1] * pi
						+ dp[i - 1][j] * (1 - pi);
			}
		}

		double ans = 0;
		for (int i = n / 2 + 1; i <= n; i++) {
			ans += dp[n][i];
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 130900
# input
n = gets.chomp.to_i
a = gets.chomp.split.map(&:to_i)
ans = 1
nowmin = a[0]

# main
if n != 1 then
  (1..n).each do |i|
    if a[i] < nowmin then
      ans += 1
      nowmin = a[i]
    end
    if nowmin == 1
      break
    end    
  end
end

# output
puts ans
  

Measured memory_bytes: 16516
//For higher stack size use g++ -O2 -std=c++11 -Wall -Wl,--stack=268435456 a.cpp -o a.exe in cmd
	#include <bits/stdc++.h>
	#include <cstdio>
	#include <cstring>
	#include <cmath>
	#include <cstring>
	#include <chrono>
	#include <complex>
	#define ll long long
	#define ld long double
	#define vi vector<int>
	#define vll vector<ll>
	#define vvi vector < vi >
	#define pii pair<int,int>
	#define pll pair<long long, long long>
	#define mod 1000000007
	#define inf 1000000000000000001;
	#define all(c) c.begin(),c.end()
	#define mp(x,y) make_pair(x,y)
	#define mem(a,val) memset(a,val,sizeof(a))
	#define eb emplace_back
	#define pb push_back
	#define f first
	#define s second
	
	using namespace std;
	int main()
	{
		std::ios::sync_with_stdio(false);
		int T;
		T=1;
		// cin.ignore(); must be there when using getline(cin, s)
		while(T--)
		{
			int n,i,j;
			cin>>n;
			string ar[n];
			map<string,int> mp;
			int maxi=0;
			for(i=0;i<n;++i)
			{
				cin>>ar[i];
				++mp[ar[i]];
				maxi=max(maxi,mp[ar[i]]);
			}
			for(auto it:mp)
			{
				if(it.s==maxi)
					cout<<it.f<<endl;
			}
		}
		return 0;
	}


Measured memory_bytes: 25472
N,M=map(int,input().split())
P=list(input().split() for _ in range(M))
manageDo={}
manageWa={}
for n in range(N):
    manageDo[str(n+1)] = 0
    manageWa[str(n+1)] = 0
wa=0
ac=0
for p in P:
    now=manageDo[p[0]]
    if p[1] == 'WA' and now == 0:
        manageWa[p[0]] += 1
    elif p[1] == 'AC' and now == 0:
        ac+=1
        wa+=manageWa[p[0]]
        manageDo[p[0]] = 1

print(ac,wa)

Measured memory_bytes: 57344
#include <stdio.h>

  int main(){
    int a,b;
    int syuu,menseki;
    scanf("%d %d",&a,&b);
    syuu = ((a*2)+(b*2));
    menseki = (a*b);
    printf("%d %d\n",menseki,syuu);
    return 0;
  }


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

struct unionFind {
  vector<int> d;  // 根： 木のサイズ x -1, それ以外： 親のID
  unionFind(int n = 0) : d(n, -1) {}
  int find(int x) {
    if (d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(int x, int y) {
    // root化しておく
    x = find(x);
    y = find(y);
    if (x == y) return false;

    // x を y に unite
    // d[x] のほうが多きい（=サイズが小さい）場合はswap
    if (d[x] > d[y]) swap(x, y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return -d[find(x)]; }
} uf;

vector<edge> G;
int V;

void kruskal() {
  double ans = 0;
  sort(G.begin(), G.end());
  for (edge e : G) {
    double w = get<0>(e);
    int s = get<1>(e), t = get<2>(e);
    if (!uf.same(s, t)) {
      uf.unite(s, t);
      ans += w;
    }
  }
  printf("%.3lf\n", ans);
}

int main() {
  while (1) {
    cin >> V;
    if (V == 0) break;
    vector<double> x(V);
    vector<double> y(V);
    vector<double> z(V);
    vector<double> r(V);
    rep(i, V) cin >> x[i] >> y[i] >> z[i] >> r[i];

    uf = unionFind(V);
    rep(i, V) uf.d[i] = -1;
    G = vector<edge>();
    rep(i, V) rep(j, V) {
      if (i == j) continue;
      double dist =
          sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) +
               (z[i] - z[j]) * (z[i] - z[j])) -
          (r[i] + r[j]);

      // 触れていない場合は廊下を作る
      // あとでkruskalで間引く
      // 触れいているときはすでにつながっていると考える
      if (dist > 0.0)
        G.push_back(edge(dist, i, j));
      else
        uf.unite(i, j);
    }
    kruskal();
  }
  return 0;
}


Measured memory_bytes: 3392
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define _GLIBCXX_DEBUG
#define rep(i, a, b) for(int i = a; i < b; i++)
#define ALL(v) v.begin(), v.end()

int main(){
    int x,a;
    cin>>x>>a;
    if(x<a) cout<<0<<endl;
    else cout<<10<<endl;
}

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

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

  int n, k;
  cin >> n >> k;
  vector<int> p(n);
  rep(i,n) cin >> p[i];
  sort(p.begin(), p.end());

  int res = 0;
  rep(i,k) res += p[i];
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 3600
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

def readinput():
    n=int(input())
    return n

def possibleCnt(n):
    cnt=0
    resu=n
    for i in range(1,n+1):
        if resu >= i:
            cnt+=1
            resu-=i
            #print(cnt,resu)
    return cnt       

def main(n):
    ansList=factorization(n)
    #print(ansList)
    count=0
    for l in ansList:
        if(l[0]!=1):
            count+=possibleCnt(l[1])
    return count    


if __name__=='__main__':
    n=readinput()
    ans=main(n)
    print(ans)


Measured memory_bytes: 9504
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < n; i++)
typedef long long ll;
using namespace std;
#define llMAX numeric_limits<long long>::max()
#define intMAX numeric_limits<int>::max()
#define d_5 100000
#define d9_7 1000000007
#define vll vector<vector<long long>>
#define vl vector<long long>
#define vi vector<int>
#define vii vector<vector<int>>
#define pb push_back
#define pf push_front
int main(void){
  int n,m;
  cin>>n>>m;
  vi a(m);
  vi b(m);
  vii c(m);
  rep(i,m){
    cin>>a[i]>>b[i];
    c[i]=vi(b[i]);
    rep(j,b[i]){
      cin>>c[i][j];
      c[i][j]--;
    }
  }
  vi dp((int)pow(2,n),7000000);
  dp[0]=0;
  rep(j,m)rep(i,(int)pow(2,n)){
    int next=0;
    if(dp[i]==7000000)continue;
    rep(k,b[j]){
      if((i/((int)pow(2,c[j][k])))%2==0){
        next+=(int)pow(2,c[j][k]);
      }
    }
    dp[i+next]=min(dp[i+next],dp[i]+a[j]);
  }
  /*rep(i,(int)pow(2,n))cout<<dp[i]<<" ";
  cout<<endl;*/
  if(dp[(int)pow(2,n)-1]==7000000){
    cout<<-1;
  }else{
    cout<<dp[(int)pow(2,n)-1];
  }
  return 0;
}

Measured memory_bytes: 384
// Problem : B - Echo
// Contest : AtCoder - AtCoder Beginner Contest 145
// URL : https://atcoder.jp/contests/abc145/tasks/abc145_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

//Macros

#define ll long long
#define db long double
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define mi map<int,int>
#define mii map<pii,int>
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define sz(x) (int)x.size()
#define mod 1000000007
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define inf 1e10
#define PI acos(-1.0)
#define int long long
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define N 100005

//Solution

void solve(){
    int n;
    string s;
    cin>>n>>s;
    if(n%2){
        cout<<"No\n";
        return;
    }
    for(int i=0;i<n/2;i++){
        if(s[i] != s[n/2+i]){
            cout<<"No\n";
            return;
        }
    }
    cout<<"Yes\n";
}

signed main(){
    io;
    //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    int tests;
    //cin>>tests;
    tests = 1;
    while(tests--){
        solve();
    }
    return 0;
}

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

int main() {
  int N,h;
  cin >> N;
  int M=N;
  for (int i=0;i<9;i++){
    h+=M%10;
    M/=10;
    if (M==0){
      break;
    }
  }
  if (N%h==0){
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<string>
#define t int t; cin>>t; while(t--)

using namespace std;

int main()
{
	int z = 0;
	string x, y;
	cin >> x >> y;
	for (int i = 0; i < x.length(), i < y.length(); i++)
	{
		if (x[i] == y[i])
		{
			z++;
		}
	}
	if (z == x.length())
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}

Measured memory_bytes: 3640
n, x = map(int, input().split())
a = list(map(int, input().split()))
b = a[:]
ans = sum(b)
for k in range(1, n):
    b_ = []
    for i in range(n):
        b_.append(min(b[i], a[i - k]))
    b = b_[:]
    ans = min(ans, k * x + sum(b))
print(ans)

Measured memory_bytes: 3316
str = gets
n = str.chomp.to_i

str = gets
x = str.split(" ").map(&:to_i)

min_tairyoku = 1000000
for i in 1 .. 100
  tairyoku = 0
  x.each{|e| tairyoku = tairyoku + (e-i)**2}
  if min_tairyoku > tairyoku
    min_tairyoku = tairyoku
  end
end

puts min_tairyoku

Measured memory_bytes: 1788
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <cstring>
#include <limits>
#include <cmath>
#include <cfloat>

#define FOR(i,b,n) for(int i=b;i<n;i++)
#define CLR(mat) memset(mat, 0, sizeof(mat))

using namespace std;
typedef pair<int, int> doll;

int n, m;
vector<doll> vc;

int solve_rec(int d, int dp[])
{
	int res = 1;
	
	if( dp[d] != 0 )
	{
		return dp[d];
	}
	else
	{
		FOR(i, 0, n+m)
		{
			if( vc[i].first < vc[d].first && vc[i].second < vc[d].second )
			{
				res = max(res, solve_rec(i, dp)+1);
			}
		}
		
		dp[d] = res;
		return res;
	}
}

int solve()
{
	int res = 1;
	int dp[1000] = {0};

	FOR(i, 0, n+m)
	{
		res = max(res, solve_rec(i, dp));
	}
	
	return res;
}
int main()
{
	while(cin >> n, n)
	{
		int res = 1;
		vc.clear();

		FOR(i, 0, n)
		{
			doll d;
			cin >> d.first >> d.second;
			
			vc.push_back(d);
		}
		
		cin >> m;
		
		FOR(i, 0, m)
		{
			doll d;
			cin >> d.first >> d.second;
			
			vc.push_back(d);
		}
		
		cout << solve() << endl;
	}
	
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<deque>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#include<iomanip>
#include<cassert>
#include<regex>
#include<bitset>
#include<complex>
#include<chrono>
#include<random>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define rrep(i,a) for(int i=(int)a-1;i>=0;--i)
#define REP(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RREP(i,a,b) for(int i=(int)a-1;i>=b;--i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;

ll gcd(ll n, ll m) {
	ll tmp;
	while (m!=0) {
		tmp = n % m;
		n = m;
		m = tmp;
	}
	return n;
}

ll lcm(ll n, ll m) {
	return abs(n) / gcd(n, m)*abs(m);//gl=xy
}
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
 
using namespace std;

vector<int>check;


bool func(int x,int y,vector<string> &s){
  REP(i,-1,2)REP(j,-1,2){
    if(i==0&&j==0)continue;
    int nx=x,ny=y;
    while((nx+i>=0)&&(nx+i<8)&&(ny+j>=0)&&(ny+j<8)){
      nx+=i;
      ny+=j;
      if(s[nx][ny]=='Q')return false;
    }
  }
  return true;
}

bool rec(int n,vector<string> &s){
  if(n==8)return true;
  if(check[n]!=-1){
    if(!func(n,check[n],s))return false;
    if(rec(n+1,s))return true;
    else return false;
  }
  else {
    rep(i,8){
      if(func(n,i,s)){
        s[n][i]='Q';
        if(rec(n+1,s))return true;
        else {
          s[n][i]='.';
        }
      }
    }
    return false;
  }
}

void solve(){
  int k;
  cin>>k;
  vector<int>x(k),y(k);
  vector<string>s(8,"........");
  rep(i,k)cin>>x[i]>>y[i],s[x[i]][y[i]]='Q';
  check.resize(8,-1);
  rep(i,k){
    check[x[i]]=y[i];
  }
  rec(0,s);
  rep(i,8)cout<<s[i]<<"\n";
}

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



Measured memory_bytes: 3232
#include <iostream>

using namespace std;

int main(){
    int N, M;
    int day=0;
    cin>>N>>M;
    int HW;

    while (M--) {
        cin>>HW;
        day=day+HW;
    }
    int ans;
    ans=N-day;
    if(ans>=0)
        cout<<ans;
    else
        cout<<-1;

}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
int H,W;

int h,w;
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> H >> W >> h >> w;

	cout << H * W - (H * w + W * h - h * w ) << endl;

}

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

const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1.0);

int main(void)
{
    ll a,b,c,ans; cin>>a>>b>>c;
    if(a%2==0 || b%2==0 || c%2==0) ans=0;
    else{
        ans = min({a*b, b*c, c*a});
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3524
N, S = map(int, input().split())
MOD = 998244353
A = list(map(int, input().split()))

# dp[i][s] : Rをiに固定した時に、和がsとなる整数列の組が何回現れるか
dp = [[0]*(S+1) for i in range(N+1)]
ans = 0

for i, a in enumerate(A, 1):
  for s in range(S+1):
    dp[i][s] = dp[i-1][s]
    dp[i][s] += s==0 or s==a
    if s >= a:
      dp[i][s] = (dp[i][s] + dp[i-1][s-a]) % MOD
  ans = (ans + dp[i][-1]) % MOD

print(ans)

Measured memory_bytes: 114908
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
template <typename T, typename U>
using P = pair<T,U>;
template <typename T>
using vt = vector<T>;
using vvi = vector<vector<int>>;

int main(){
  int N,K;
  cin >> N >> K;
  map<int,int> map;

  rep (i,N){
      int num;
      cin >> num;
      map[num]++;
  }

  int s = map.size(), cnt = 0;
  vt<int> m;
  for(auto& it : map){
      m.push_back(it.second);
  }
  
  map.clear();
  sort(m.begin(),m.end());
  rep(i,N){
    if(s <= K) break;
    cnt += m[i];
    s--;
  }

  cout << cnt << endl;
  return 0;
}


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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

bool visited[200005];
ll ans[200005];

void dfs(Graph &graph, int v, vector<ll> &counter, ll plus) {

    visited[v] = true;
    ans[v] += counter[v] + plus;
    for (int u : graph[v]) {
        if (!visited[u]) {
            dfs(graph, u, counter, plus + counter[v]);
        }
    }
}

void Main() {
    int N, Q;
    cin >> N >> Q;
    Graph graph(N);
    rep(i, N - 1) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    vector<ll> counter(N, 0);
    rep(q, Q) {
        int p, x;
        cin >> p >> x;
        p--;
        counter[p] += x;
    }
    dfs(graph, 0, counter, 0);
    rep(i, N) {
        cout << ans[i] << ' ';
    }
}

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


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

const int N = 1e5+5;
vector<int> heights;
int cache[N];
int n,k;

int solve(int idx){
	if( idx >= n-1 ){ return 0; }
	if( cache[idx] != -1 ){ return cache[idx]; }
	int &ans = cache[idx];
	int a1 = 1e9;
	for(int j=idx+1; j< min(n,idx+k+1); ++j){
		a1 = min(a1, solve(j) + abs(heights[j]-heights[idx]));
	}
	ans = a1;
	return ans;
}






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

	cin>>n>>k;
	heights.resize(n+10);
	for(int i=0; i<n; ++i){
		cin>>heights[i];
	}
	memset(cache,-1,sizeof(cache));
	int ans = solve(0);
	cout<<ans<<'\n';
	return 0;
}


Measured memory_bytes: 7296
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set> 
#include <map>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iomanip>
#define rep(i,n) for(int i=0; i<(n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1001001001; // > 10^9
const int MOD = (int)1e9 + 7;
const ll INFLL = 1001001001001001001;  // > 10^18
const ll MODLL = (ll)1e9 + 7;
const double EPS = 1e-9;

int main () {
    
    ll n,ma,mb; cin >>n>>ma>>mb;
    vector<ll> a(n); vector<ll> b(n); vector<ll> c(n);
    rep(i,n) cin >> a[i] >> b[i] >> c[i];

    ll n1 = n/2;
    vector<P> pairs1((1<<n1));

    ll ans1 = INFLL;
    for (ll s = 0; s < (1<<n1); s++) {
        ll suma = 0;
        ll sumb = 0;
        ll sumc = 0;
        for (ll i = 0; i < n1; i++) {
            if (s & (1<<i)) {
                suma += a[i];
                sumb += b[i];
                sumc += c[i];
            }
        }
        pairs1[s] = P((ma+mb)*suma - ma*(suma+sumb), sumc);
        if ((ma+mb)*suma - ma*(suma+sumb) == 0 && sumc > 0 && ans1 > sumc) {
            ans1 = sumc;
        } 
    }

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

    ll ans = INFLL;
    for (ll s = 0; s < (1<<(n-n1)); s++) {
        ll suma = 0;
        ll sumb = 0;
        ll sumc = 0;
        for (ll i = 0; i < (n-n1); i++) {
            if (s & (1<<i)) {
                suma += a[n1 + i];
                sumb += b[n1 + i];
                sumc += c[n1 + i];
            }
        }
        ll m = ma*(suma+sumb) - (ma+mb)*suma;
        ll ok = (1<<n1);
        ll ng = -1;
        while (abs(ng-ok)>1) {
            ll mid = (ok+ng)/2;
            if (m <= pairs1[mid].first) {
                ok = mid;
            } else {
                ng = mid;
            } 
        }
        if (m == pairs1[ok].first) {
            if (ans > sumc + pairs1[ok].second && sumc + pairs1[ok].second > 0) {
                ans = sumc + pairs1[ok].second;
            } 
        } 
    }

    if (ans == INFLL && ans1 == INFLL) {
        cout << -1 << endl;
    } else {
        cout << min(ans, ans1) << endl;
    } 

    return 0;
}



Measured memory_bytes: 8448
<?php
  fscanf(STDIN, "%d %d", $N, $L);

  $smallest = PHP_INT_MAX;
  for ($i = 0; $i < $N; $i++) {
    $a[$i] = $L + $i;
    $b[$i] = abs($a[$i]);
    if ($smallest > $b[$i]) {
        $smallest = $b[$i];
        $smallest_i = $i;
    }
  }
  $total = array_sum($a);
  $pie = $total - $a[$smallest_i];
  echo $pie;


Measured memory_bytes: 4728
Roman = { 'I'=>1, 'V'=>5, 'X'=>10, 'L'=>50, 'C'=>100, 'D'=>500, 'M'=>1000 }
while gets
    array = $_.chomp.scan(/./).map{|x| Roman[x]}
    (0..array.length-2).each do |i|
        if array[i+1] > array[i]
            array[i] = -array[i]
        end
    end

    puts array.inject(0){|sum, x| sum + x}
end

Measured memory_bytes: 6104
from collections import deque


def main():
    d = deque()
    for _ in range(int(input())):
        command = input()
        if command[0] == 'i':
            d.appendleft(command[7:])
        elif command[6] == ' ':
            try:
                d.remove(command[7:])
            except ValueError:
                pass
        elif len(command) == 11:
            d.popleft()
        else:
            d.pop()
    print(*d)


if __name__ == '__main__':
    main()



Measured memory_bytes: 69740
a,b,c,d=map(int,input().split())
time=0
if b<=c or d<=a:
    pass
elif a<=c<=b<=d:
    time=b-c
elif a<=c<=d<=b:
    time=d-c
elif c<=a<=b<=d:
    time=b-a
else:
    time=d-a
print(time)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define ll  long long
#define ff first
#define ss second
#define pb push_back
#define pp pair<ll,ll>
#define maxn 200005
#define db double
#define mod 1000000007
#define ub upper_bound
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,b,a) for(ll i=b;i>=a;i--)
using namespace std;
void solve()
{
	string s;
	cin >> s;
	ll n=s.size(),ans=0;
	ll pre[2019];
	memset(pre,0,sizeof(pre));
	ll sum=0,base=1;
	repr(i,n-1,0)
	{
		sum += base*(s[i]-'0');
		base *= 10;
		base%=2019;
		sum %= 2019;
		ans += pre[sum];
		if(sum == 0)
			ans++;
		pre[sum]++;
	}
	cout << ans ;
}		
int main()
{
	ll t=1,i=1;
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);	
    std::cout.precision(10);
    std::cout.setf( std::ios::fixed, std:: ios::floatfield ); 
	//cin >> t;
	//cin >> n;
	while(i<=t)
	{
		solve();
		i++;
	}
	return 0;
}



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

N,K=map(int,input().split())
d=[0]*K
A=[]
B=set()
for i in range(K):
    d[i]=int(input())
    A.append(list(map(int,input().split())))
    for j in A[i]:
        B.add(j)

print(N-len(B))


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

int main(){

    // omajinai
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    // omajinai

    ll x;
    cin >> x;

    ll ans;

    if(x % 11 > 6){
        ans = x / 11 * 2 + 2;
    }else if(x % 11 > 0){
        ans = x / 11 * 2 + 1;
    }else{
        ans = x / 11 * 2;
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define pb push_back
#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define ll long long
#define REP(i,a,b) for(int i=a;i<b;i++)
#define RREP(i,a,b) for(int i=a;i>b;i--)
#define mkp(a,b) make_pair(a,b)
#define all(v) v.begin(),v.end()
using namespace std;
bool compare(pair<int,int>& p1,pair<int,int>& p2)
{
    return p1.second<p2.second;
}
int main()
{
    fastio
    ll n;
    cin>>n;
    ll sum=0;
    map<int,int> m;
    REP(i,0,n)
    {
        ll temp;
        cin>>temp;
        sum+=temp;
        m[temp]++;
    }
    ll q;
    cin>>q;
    while(q--)
    {
        ll b,c;
        cin>>b>>c;
        if(m.find(b)!=m.end())
        {
            sum=sum-m[b]*b+m[b]*c;
            m[c]+=m[b];
            m[b]=0;
            cout<<sum<<"\n";
            
        }
        else
            cout<<sum<<"\n";
    }
}

Measured memory_bytes: 7428
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int main()
{
    int N, X; cin >> N >> X;
    vector<int> L(N); for (auto &l : L) cin >> l;
    int ans = 1;
    int curr = 0;
    for (int i = 0; i < N; i++) {
        curr += L[i];
        if (curr <= X) ans++;
    }
    cout << ans << '\n';
    return 0;
}


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

int main()
{
	int n, ans = 1, cur, min_sofar;
	cin >> n >> min_sofar;
	while(--n){
		cin >> cur;
		if(cur < min_sofar){
			++ans;
			min_sofar = cur;
		}
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        int ans = 0;
        for(int i=1; i<6; i++){
            int tmp = sc.nextInt();
            if(tmp==0){
                ans = i;
            }
        }
        
        System.out.println(ans);
    }
}


Measured memory_bytes: 35408
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

int main(){
  string s;
  cin >> s;
  map<char,int> mp;
  for(int i=0;i<3;i++) mp[s[i]]++;
  if(mp['a']==1 && mp['b']==1 && mp['c']==1) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String str[] = br.readLine().split(" ");

		int n = Integer.parseInt(str[0]);
		int k = Integer.parseInt(str[1]);

		System.out.println(lcm(n, k));
	}

	static long gcd(long m, long n) {
		if (m < n)
			return gcd(n, m);
		if (n == 0)
			return m;
		return gcd(n, m % n);
	}

	static long lcm(long m, long n) {
		return m * n / gcd(m, n);
	}
}


Measured memory_bytes: 23252
import sys
import itertools
import numpy as np
import networkx as nx

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

N, M = map(int, readline().split())
S = np.frombuffer(read(), 'S1').reshape(N, -1)[:, :M].astype('U1')

A = []
B = []
E = []

for i, j in itertools.product(range(N), range(M)):
    if S[i, j] == '#':
        continue
    elif (i + j) & 1:
        A.append((i, j))
    else:
        B.append((i, j))

for i, j in A:
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        i1, j1 = i + dx, j + dy
        if 0 <= i1 < N and 0 <= j1 < M and S[i1, j1] != '#':
            E.append(((i, j), (i1, j1)))

G = nx.Graph()
G.add_nodes_from(A, bipartite=0)
G.add_nodes_from(B, bipartite=1)
G.add_edges_from(E)

M = nx.bipartite.maximum_matching(G, A)
for key, item in M.items():
    i, j = key
    i1, j1 = item
    if i1 == i + 1:
        a, b = 'v', '^'
    elif i1 == i - 1:
        a, b = '^', 'v'
    elif j1 == j + 1:
        a, b = '>', '<'
    else:
        a, b = '<', '>'
    S[i, j], S[i1, j1] = a, b

print(len(M) // 2)
for row in S:
    print(''.join(row))


Measured memory_bytes: 69828
N = int(input())
A  = list(map(int,input().split()))
now = 0
sumA = sum(A)
for i in range(N):
    now += A[i]
    if now == sumA/2:
        print(0)
        break
    elif now > sumA/2:
        test1 = now-sum(A[i+1:])
        test2 = sum(A[i:])-(now-A[i])
        print(int(min([test1,test2])))    
        break

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

using namespace std;

using ll = long long;

struct Point {
   int x, y;
   Point(int x = 0, int y = 0) :
      x(x), y(y) {}
   bool operator < (const Point &p) const {
      return x < p.x || (x == p.x && y < p.y);
   }
   Point operator + (const Point &p) const {
      return Point(x + p.x, y + p.y);
   }
   Point operator - (const Point &p) const {
      return Point(x - p.x, y - p.y);
   }
   ll operator * (const Point &p) const {
      return (ll) x * p.y - (ll) y * p.x;
   }
   ll norm() {
      return (ll) x * x + (ll) y * y;
   }
};

vector<Point> minkowski(vector<vector<Point>> pss) {
   vector<Point> ans(1, Point());
   vector<Point> go;
   int cnt = 0;
   for (auto &ps : pss) {
      rotate(ps.begin(), min_element(ps.begin(), ps.end()), ps.end());
      ans[0] = ans[0] + ps[0];
      int sz = ps.size();
      for (int i = 0; i < sz; ++i) {
         go.emplace_back(ps[(i + 1) % sz] - ps[i]);
      }
   }
   sort(go.begin(), go.end(), [&](Point p, Point q) {
      bool fp = p < Point();
      bool fq = q < Point();
      if (fp ^ fq) {
         return fq;
      } else {
         return p * q > 0;
      }
   });
   for (auto p : go) {
      ans.emplace_back(ans.back() + p);
   }
   return ans;
}

int main() {
   ios_base::sync_with_stdio(false);
   int n;
   cin >> n;
   vector<vector<Point>> pss;
   while (n--) {
      int x, y;
      cin >> x >> y;
      if (x || y) {
         pss.emplace_back(vector<Point> {{0, 0}, {x, y}});
      }
   }
   vector<Point> ps = minkowski(pss);
   ll ans = 0;
   for (auto p : ps) {
      ans = max(ans, p.norm());
   }
   cout << fixed << setprecision(10) << sqrt(ans) << "\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define show(x) cerr << #x << " = " << x << endl
using namespace std;

typedef long long ll;
typedef pair<int, int> pairs;
const ll INF = 1ll << 60;
const int N = 404040;
const int MOD = 1000000007;

inline char get(void) {
	static char buf[100000], *S = buf, *T = buf;
	if (S == T) {
		T = (S = buf) + fread(buf, 1, 100000, stdin);
		if (S == T) return EOF;
	}
	return *S++;
}
template<typename T>
inline void read(T &x) {
	static char c; x = 0; int sgn = 0;
	for (c = get(); c < '0' || c > '9'; c = get()) if (c == '-') sgn = 1;
	for (; c >= '0' && c <= '9'; c = get()) x = x * 10 + c - '0';
	if (sgn) x = -x;
}

struct edge {
	int to, key, next;
	edge(int t = 0, int k = 0, int n = 0): to(t), key(k), next(n) {};
} G[N];
int n, m, x, y, z, s, t, gcnt, ans;
ll dis[N], sid[N];
int head[N], vis[N], onw[N];
queue<int> Q;
vector<int> E[N], B[N];
int f[N], g[N];

inline void addEdge(int from, int to, int key) {
	G[++gcnt] = edge(to, key, head[from]); head[from] = gcnt;
	G[++gcnt] = edge(from, key, head[to]); head[to] = gcnt;
}
inline void shortestPath(ll *dis, int s) {
	for (int i = 1; i <= n; i++) {
		dis[i] = INF; vis[i] = 0;
	}
	Q.push(s); vis[s] = 1; dis[s] = 0;
	while (!Q.empty()) {
		int x = Q.front(); Q.pop();
		for (int i = head[x]; i; i = G[i].next)
			if (dis[G[i].to] > dis[x] + G[i].key) {
				dis[G[i].to] = dis[x] + G[i].key;
				if (!vis[G[i].to]) {
					vis[G[i].to] = 1;	Q.push(G[i].to);
				}
			}
		vis[x] = 0;
	}
}
inline void add(int &x, int a) {
	x = (x + a >= MOD) ? x + a - MOD : x + a;
}
inline void sub(int &x, int a) {
	x = (x < a) ? x - a + MOD : x - a;
}
inline void dfs1(int u) {
	vis[u] = 1;
	for (int to: E[u]) {
		if (!vis[to]) dfs1(to);
		add(f[u], f[to]);
	}
}
inline void dfs2(int u) {
	vis[u] = 1;
	for (int to: B[u]) {
		if (!vis[to]) dfs2(to);
		add(g[u], g[to]);
	}
}
inline int sqr(int x) {
	return (ll)x * x % MOD;
}

int main(void) {
	read(n); read(m);
	read(s); read(t);
	for (int i = 1; i <= m; i++) {
		read(x); read(y); read(z);
		addEdge(x, y, z);
	}
	shortestPath(dis, s);
	shortestPath(sid, t);
	for (int i = 1; i <= n; i++)
		onw[i] = (dis[i] + sid[i] == dis[t]);
	for (int i = 1; i <= n; i++)
		if (onw[i])
			for (int j = head[i]; j; j = G[j].next)
				if (onw[G[j].to] && dis[G[j].to] == dis[i] + G[j].key)
					E[i].push_back(G[j].to);
	for (int i = 1; i <= n; i++)
		if (onw[i])
			for (int j = head[i]; j; j = G[j].next)
				if (onw[G[j].to] && sid[G[j].to] == sid[i] + G[j].key)
					B[i].push_back(G[j].to);
	
	for (int i = 1; i <= n; i++) vis[i] = 0;
	vis[t] = 1; f[t] = 1; dfs1(s);
	for (int i = 1; i <= n; i++) vis[i] = 0;
	vis[s] = 1; g[s] = 1; dfs2(t);
	for (int i = 1; i <= n; i++)
		if (onw[i] && dis[i] * 2 == dis[t])
			add(ans, sqr((ll)f[i] * g[i] % MOD));
	for (int i = 1; i <= n; i++)
		if (onw[i] && dis[i] * 2 < dis[t])
			for (int j: E[i])
				if (dis[j] * 2 > dis[t])
					add(ans, (ll)g[i] * f[j] % MOD * g[i] % MOD * f[j] % MOD);
	ans = (sqr(f[s]) - ans + MOD) % MOD;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 45824
#include <bits/stdc++.h>
#define fastIO ios::sync_with_stdio(NULL); cin.tie(NULL);

using namespace std;
const int N = 2E3+7;
const int p = 1E9+7;

long long f[N][N];
char a[N][N];
int n,m;

int main()
{
    fastIO
    cin>>n>>m;
    
    for (int i = 1;i <= n;++i) 
        for (int j = 1;j <= m;++j) cin>>a[i][j];
    
    f[1][1] = 1;
    for (int i = 1;i <= n;++i)
        for (int j = 1;j <= m;++j)
            if (a[i][j] == '.')
            {
                if (a[i-1][j] == '.' && i-1 >= 0) f[i][j] += f[i-1][j];
                if (a[i][j-1] == '.' && j-1 >= 0) f[i][j] += f[i][j-1];
                f[i][j] = f[i][j] % p;
            }
    
    cout<<f[n][m];
}

Measured memory_bytes: 17340
x = int(input())

if 400 <= x <= 599:
    print(8)
if 600 <= x <= 799:
    print(7)
if 800 <= x <= 999:
    print(6)
if 1000 <= x <= 1199:
    print(5)
if 1200 <= x <= 1399:
    print(4)
if 1400 <= x <= 1599:
    print(3)
if 1600 <= x <= 1799:
    print(2)
if 1800 <= x <= 1999:
    print(1)


Measured memory_bytes: 9184
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;


int main(){
  int n;
  long long ans = 1, tot=1;
  cin >> n;
  int i;
  for(i=0;i<n;i++)
  {
    tot = tot*10;
    tot %= mod;
  }
 for(i=0;i<n;i++)
  {
    ans = ans*8;
    ans %= mod;
  }
  long long a = 2;
  for(i=0;i<n;i++)
  {
    a=a*9;
    a%=mod;
  }
  cout<<(tot+ans+-a+mod*1LL)%mod<<endl;
  return 0;
}


Measured memory_bytes: 3552
//#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <complex>
#include <bitset>
#include <functional>
#include <stack>
#include <regex>
#include <tuple>
#include <iomanip>


#define int long long
#define REP(i,l,r) REPEAT(i,l,r,true) // [l, r)
#define rep(i,n) REP(i,0,n)           // [0, n)
#define REPEAT(i,l,r,condition) for(int i=(condition)?l:r-1;(condition)?i<r:i>=l;(condition)?++i:--i) // false<-[l, r)->true
#define all(e) e.begin(),e.end()
#define rall(e) e.rbegin(),e.rend()
#define pb push_back
#define fs first
#define sc second
#ifdef LOCAL
#define show(...) cerr<<#__VA_ARGS__<<" = ";_DEBUG(__VA_ARGS__)
#define showlr(n,l,r) cerr<<#n<<" = ";for(int i=l;i<r;i++){cerr<<n[i]<<", ";}cerr<<endl // [l, r)
#else
#define show(...)
#define showlr(n,l,r)
#endif

#define YN(condition) puts((condition)?"YES":"NO")
#define Yn(condition) puts((condition)?"Yes":"No")
#define yn(condition) puts((condition)?"yes":"no")
#define YES puts("YES")
#define Yes puts("Yes")
#define yes puts("yes")
#define NO  puts("NO")
#define No  puts("No")
#define no  puts("no")

#define case(i) printf("Case #%lld: ",i)

using namespace std;

using vi=vector<int>;
using pint=pair<int,int>;

struct io{io(){cin.tie(0);ios::sync_with_stdio(false);cout.tie(0);cout<<fixed<<setprecision(20);}}io;

template<class T> istream& operator >>(istream &is, vector<T> &v){for(T &e:v)is>>e;return is;}
template<class T> ostream& operator <<(ostream &os, vector<T> v){os<<"{";for(T &e:v)os<<e<<(v.size()-(int)(&e-&v[0])>1?", ":"");os<<"}";return os;}

void _DEBUG(){}
template<typename H,typename... T> void _DEBUG(H a,T...b){cerr<<a<<(sizeof...(b)?",":"\n");_DEBUG(b...);}

inline void in(){}
template<typename H,typename... T>void in(H &a, T&... b){cin>>a;in(b...);}
inline void out(){}
template<typename H,typename... T> void out(H a, T... b){cout<<a<<(sizeof...(b)?" ":"\n");out(b...);}

template<class T> void resz(int n,T& v){v.resize(n);}
template<class H,class... T> void resz(int n,H& a,T&... b){a.resize(n);resz(n,b...);}

template<typename V,typename H> void resize(vector<V>& v,const H a){v.resize(a);}
template<typename V,typename H,typename... T> void resize(vector<V>& v,const H& a,const T... b){v.resize(a);for(auto &v:v) resize(v,b...);}

const int INF=1LL<<55;
const int MOD=1000000007;
const double EPS=1e-8;
/*------------end of definitions------------*/

int r,D,x;

signed main(){

    in(r,D,x);
    rep(i,10){
        x=x*r-D;
        out(x);
    }

    return 0;
}


Measured memory_bytes: 888
#include<stdio.h>
int main(void){
    char S[2];
    int i,a,b,c;
    b=0;
    gets(S);
    for(i=0;i<3;i++){
        if(S[i]=='o'){
            b++;
        }
    }
    c=700+(b*100);
    printf("%d\n",c);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define mod (int)1000000007
#define MOD (int)10000000007
#define X 1001100011100001111ll
#define M 26388279066623ll
#define all(a) a.begin(),a.end()
#define for0(i, n) for (int i = 0; i < n; i++)
#define for0e(i, n) for (int i = 0; i <= n; i++)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define loop(i,a,b) for (int i = a; i < b; i++)
#define bloop(i,a,b) for (int i = a ; i>=b;i--)
#define tc(t) int t; cin >> t; while (t--)
#define ll long long int
#define pb emplace_back
#define fio ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define in(x) scanf("%d", &x)
#define rr return 0
#define prec(n) fixed<<setprecision(n)
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define inf (int)(1e18)
#define ini(a, i) memset(a, i, sizeof(a))
#define vi vector<int> 
#define F first
#define S second
#define pi pair<int, int>
#define ppi pair<pair<int,int> , int >
#define vii vector<pi>
const int MAXN = (int)((1e5) + 100);
int max(int a,int b){if(a>b) return a; else return b;}
int min(int a,int b){if(a<b) return a; else return b;} 
int gcd(int a,int b) { if (a == 0) return b; return gcd(b%a, a);}
int cbrt(int x){ int lo=1,hi=min(2000000ll,x);while(hi-lo>1){int mid=(lo+hi)/2;if(mid*mid*mid<x){lo=mid;}else hi=mid;}if(hi*hi*hi<=x) return hi;else return lo;} 
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const int N =  (int)(1e6+5); 
// ========================================================
signed main(){
  #ifndef ONLINE_JUDGE
  //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);
  #endif
  fio;
    int n;
    cin>>n;
    queue<ll> q;
    ll x;
    for1(i,9)   q.push(i);
    while(n--){
        x = q.front();q.pop();
        if(x%10 != 0){
            q.push(10*x+(x%10)-1);
        } 
        q.push(10*x+(x%10));
        if(x%10 != 9){
            q.push(10*x + (x%10)+1);
        }
    }
    cout<<x<<endl;
  rr;
}



Measured memory_bytes: 4764
#include <iostream>
using namespace std;
int main(){
  int map[1500000];
  long n,a,b,ans;
 
  while(1){
 cin >>n>>a>>b; 
   if(n==0&&a==0&&b==0) break;
    for(long i=1;i<n+1;i++){
      map[i]=1;
    }
    map[0]=0;
    for(long i=0;i<n+1;i++){
      if(map[i]==0) {
	map[i+a]=0;
	map[i+b]=0;}
    }
    ans=0;
    for(long i=0;i<n+1;i++){
      ans+=map[i];
    }
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 6424
// template version 1.15
using namespace std;
#include <bits/stdc++.h>

// varibable settings
#define int long long
const int INF=1e18;

// define basic macro {{{
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define _rrep(i,n) rrepi(i,0,n)
#define rrepi(i,a,b) for(int i=(int)((b)-1);i>=(int)(a);--i)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)
#define each(i,a) for (auto&& i : a)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define mt(a, b, c) make_tuple(a, b, c)
#define ub upper_bound
#define lb lower_bound
#define posl(A, x) (lower_bound(all(A), x)-A.begin())
#define posu(A, x) (upper_bound(all(A),x)-A.begin())
template<class T> inline void chmax(T &a, const T &b) { if((a) < (b)) (a) = (b); }
template<class T> inline void chmin(T &a, const T &b) { if((a) > (b)) (a) = (b); }

#define divceil(a,b) ((a)+(b)-1)/(b)
#define is_in(x, a, b) ((a)<=(x) && (x)<(b))
#define uni(x) sort(all(x));x.erase(unique(all(x)),x.end())
#define slice(l, r) substr(l, r-l)

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> iii;

template<typename T> using PQ = priority_queue<T, vector<T>, greater<T>>;
struct Fast { Fast(){ std::cin.tie(0); ios::sync_with_stdio(false); } } fast;

#if defined(PCM) || defined(LOCAL)
    #include "lib/dump.hpp"
#else
    #define dump(...) 42
    #define dump_1d(...) 42
    #define dump_2d(...) 42
    #define cerrendl 42
#endif
//}}}

signed main() {
    int n;cin>>n;
    vi a(n), b(n), c(n);
    rep(i, n){
        cin>>a[i]>>b[i]>>c[i];
    }

    vvi dp(3, vi(n));
    dp[0][0] = a[0];
    dp[1][0] = b[0];
    dp[2][0] = c[0];

    rep(i, 1, n){
        chmax(dp[0][i], max(dp[1][i-1]+a[i], dp[2][i-1]+a[i]));
        chmax(dp[1][i], max(dp[0][i-1]+b[i], dp[2][i-1]+b[i]));
        chmax(dp[2][i], max(dp[0][i-1]+c[i], dp[1][i-1]+c[i]));
    }
    cout << max({dp[0][n-1], dp[1][n-1], dp[2][n-1]}) << endl;
    return 0;
}


Measured memory_bytes: 5760
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <cstring>

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

int n;
ll ans;

int main() {
    cin >> n;

    for (ll i = 1; i <= n; i++){
        ll m = n/i;
        ans += i*(1+m)*m/2;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3620
#include <iostream>

class Dice {
private:
    int n, s, w, e, t, b;
public:
    Dice(int u, int v, int w, int x, int y, int z);
    ~Dice() {};

    void north();
    void south();
    void west();
    void east();
    void left();
    void right();
    int get_top() { return this->t; };
};

Dice::Dice(int u, int v, int w, int x, int y, int z) {
    this->t = u;
    this->s = v;
    this->e = w;
    this->w = x;
    this->n = y;
    this->b = z;
}

void Dice::north() {
    int tmp = this->n;
    this->n = this->t;
    this->t = this->s;
    this->s = this->b;
    this->b = tmp;
}

void Dice::south() {
    int tmp = this->s;
    this->s = this->t;
    this->t = this->n;
    this->n = this->b;
    this->b = tmp;
}

void Dice::west() {
    int tmp = this->w;
    this->w = this->t;
    this->t = this->e;
    this->e = this->b;
    this->b = tmp;
}

void Dice::east() {
    int tmp = this->e;
    this->e = this->t;
    this->t = this->w;
    this->w = this->b;
    this->b = tmp;
}

void Dice::left() {
    int tmp = this->e;
    this->e = this->s;
    this->s = this->w;
    this->w = this->n;
    this->n = tmp;
}

void Dice::right() {
    int tmp = this->e;
    this->e = this->n;
    this->n = this->w;
    this->w = this->s;
    this->s = tmp;
}

int main() {
    unsigned int n;
    std::string s;
    while (std::cin >> n, n != 0) {
        unsigned int res=0;
        Dice dice(1, 2, 3, 4, 5, 6);
        res += dice.get_top();
        for (int i=0; i<n; ++i) {
            std::cin >> s;
            if (s == "North") {
                dice.north();
            } else if (s == "East") {
                dice.east();
            } else if (s == "West") {
                dice.west();
            } else if (s == "South") {
                dice.south();
            } else if (s == "Left") {
                dice.left();
            } else if (s == "Right") {
                dice.right();
            }
            res += dice.get_top();
        }
        std::cout << res << std::endl;
    }
    return 0;
}



Measured memory_bytes: 3160
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

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

const ll mod=1000000007;

ll countBits(ll in){
  int res=0;
  for(;in>0;in>>=1){
    if((in&0x01)!=0){
      res++;
    }
  }
  return res;
}

template<typename T>
void show2dVector(vector<vector<T>>& v){
  for(int i=0;i<v.size();i++){
    int m=v[i].size();
    cout<<i<<" : ";
    for(int j=0;i<m;i++){
      cout<<v[i][j]<<" ";
    }
    cout<<endl;
  }
}

void bfs(const vector<vector<int>>&g, int v, vector<bool>& seen){
  seen[v]=true;
  cout<<v<<" ";
  for(auto next: g[v]){
    if(seen[next]){
      continue;
    }
    bfs(g,next,seen);
  }
}

bool dfs(vector<vector<int>> &g,int start,int goal,vector<bool>&seen){
  bool res=false;
  seen[start]=true;
  if(start==goal){
    return true;
  }
  for(auto next: g[start]){
    if(seen[next]){
      continue;
    }
    res=dfs(g,next,goal,seen);
    if(res){
      break;
    }
  }
  return res;
}

ll gcd(ll a,ll b) {
  return b? gcd(b,a%b): a;  
}
ll lcm(ll a,ll b) {
  return a*b/gcd(a,b);
}
bool isLowerCase(char c){
  return (c>='a'&&c<='z');
}

char toLowerCase(char c){
  if(isLowerCase(c)){
    return c;
  }else{
    return c+'a'-'A';
  }
}
char toUpperCase(char c){
  if(isLowerCase(c)){
    return c-('a'-'A');
  }else{
    return c;
  }
}
ll powm(ll a,ll n, ll m){
  ll ret=1;
  while(n>0){
    if(n%2==1){
      ret=(ret*a)%m;
    }
    n>>=1;
    a=(a*a)%m;
  }
  return ret;
}

const string yesno(bool ans){
  return (ans?"Yes":"No");
}
void func(vector<int>& l, int depth, int idx){
  ;
}
int main() {
  int n,a,b;cin>>n>>a>>b;
  int ans1=min(a,b);
  int ans2=max(0,a+b-n);
  cout<<ans1<<" "<<ans2<<endl;
  return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <string>

int main(){
	while(1){
		std::string cards;
		int m, h;
		std::cin >> cards >> m;
		if(cards == "-")
			break;
		for(int i=0; i<m; i++){
			std::cin >> h;
			cards = cards.substr(h) + cards.substr(0, h);
		}
		std::cout << cards << std::endl;
	}
	return 0;
}

Measured memory_bytes: 1216
program main

  implicit none
  character(100) :: s
  integer :: i,n, ls

  read(*,*) s
  ls = len_trim( s )

  n = 0
  do i = 1, ls/2
    if ( s(i:i) == s(ls+1-i:ls+1-i) ) then
    else
      n = n + 1
    end if
  end do
  print*, n

end program main

Measured memory_bytes: 640