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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
using llint = long long;
using vint = vector<int>;

int main () {
    int a, b, c, d; cin >> a >> b >> c >> d;
    if (a + b > c + d) cout << "Left\n";
    else if (a + b < c + d) cout << "Right\n";
    else cout << "Balanced\n";
}

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

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

  vector<int> a(n);
  //vectorに全入力値を代入する
  rep(i,n) cin >> a[i];

  //配列aの偶数値が3か5で割り切れるか検証する
  int ans = 0;
  rep(i,n) {
    if (a[i]%2 == 0) {
      if (a[i]%3 != 0 && a[i]%5 != 0) {
        ++ans;
        break;
      }
    }
  }

  if (ans == 0) cout << "APPROVED" << endl;
  else cout << "DENIED" << endl;
}

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

#ifdef _DEBUG
#define debug(x) cerr << "line: " << __LINE__ << ", func: " << __func__ << " ->  " << #x << " = " << x << endl
#else
#define debug(x)
#endif

#define all(s) begin(s), end(s)
#define rall(s) rbegin(s), rend(s)
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = ((a)-1); i >= (b); i--)
#define pb push_back
#define sz(a) int((a).size())
#define put(a) ((cout) << (a) << (endl))
#define putf(a, n) ((cout) << (fixed) << (setprecision(n)) << (a) << (endl))
#define deg2rad(x) (((x)*PI) / (180.0))
#define rad2deg(x) (((x) * (180.0)) / PI)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i_i = pair<int, int>;
using ll_ll = pair<ll, ll>;
using d_ll = pair<double, ll>;
using ll_d = pair<ll, double>;
using d_d = pair<double, double>;

static constexpr ll LL_INF = 1LL << 60;
static constexpr int I_INF = 1 << 28;
static constexpr double PI = static_cast<double>(3.14159265358979323846264338327950288);
static constexpr double EPS = numeric_limits<double>::epsilon();

static map<type_index, const char* const> scanType = {
    {typeid(int), "%d"}, {typeid(ll), "%lld"}, {typeid(double), "%lf"}, {typeid(char), "%c"}};

template <class T> static void scan(vector<T>& v);
[[maybe_unused]] static void scan(vector<string>& v, bool isWord = true);
template <class T> static inline bool chmax(T& a, T b);
template <class T> static inline bool chmin(T& a, T b);
template <class T> static inline T gcd(T a, T b);
template <class T> static inline T lcm(T a, T b);
template <class A, size_t N, class T> static void Fill(A (&arr)[N], const T& val);
template <class T> T mod(T a, T m);

int main(int argc, char* argv[]) {
  long long N;
  scanf("%lld", &N);
  long long M;
  scanf("%lld", &M);

  ll a = (N - M) * 100;
  ll b = M * 1900;
  ll ans = (a + b) * ll(pow(2, M));
  put(ans);
  return 0;
}

template <class T> static void scan(vector<T>& v) {
  auto tFormat = scanType[typeid(T)];
  for (T& n : v) {
    scanf(tFormat, &n);
  }
}

static void scan(vector<string>& v, bool isWord) {
  if (isWord) {
    for (auto& n : v) {
      cin >> n;
    }
    return;
  }

  int i = 0, size = v.size();
  string s;
  getline(cin, s);

  if (s.size() != 0) {
    i++;
    v[0] = s;
  }

  for (; i < size; ++i) {
    getline(cin, v[i]);
  }
}

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

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

template <class T> inline T gcd(T a, T b) { return __gcd(a, b); }

template <class T> inline T lcm(T a, T b) { return (a * b) / gcd(a, b); }

template <class A, size_t N, class T> void Fill(A (&arr)[N], const T& val) {
  std::fill((T*)arr, (T*)(arr + N), val);
}

template <class T> T mod(T a, T m) { return (a % m + m) % m; }


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

ans = 0
ama = 0

for i in range(1, 10):
    ans = n / i
    ama = n % i

    if i == 9 and ama != 0:
        print("No")
    if i <= 9 and ans <= 9 and ama == 0:
        print("Yes")
        exit()

Measured memory_bytes: 9176
import java.util.Scanner;

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

        int n1 = sc.nextInt();
        int n2 = sc.nextInt();
        int n3 = sc.nextInt();

        int tmp;

        if(n1 > n2) {
            tmp = n1;
            n1 = n2;
            n2 = tmp;
        }
        if(n1 > n3) {
            tmp = n1;
            n1 = n3;
            n3 = tmp;
        }
        if(n2 > n3) {
            tmp = n2;
            n2 = n3;
            n3 = tmp;
        }

        System.out.println(n1 + " " + n2 + " " + n3);
    }
}


Measured memory_bytes: 26200
import Control.Applicative
import Control.Monad

main = do
  n <- (read::String->Int) <$> getLine
  v <- replicateM n ((map read . words) <$> getLine)
  mapM_ putStrLn $ map (que [0] [0]) v
            
que :: [Int] -> [Int] -> [Int] -> String
que _ _ [] = "YES"
que xa@(x:xs) ya@(y:ys) (r:rs)
  | r>x = que (r:xa) ya rs
  | r>y = que xa     (r:ya) rs
  | otherwise         = "NO"

Measured memory_bytes: 4000
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  while(cin>>n,n!=0){
    vector<int> point(n);
    for(int i=0;i<n;i++)
      cin>>point[i];
    sort(point.begin(),point.end());
    int ave=0;    
    for(int i=1;i<n-1;i++)
      ave+=point[i];
    ave/=(n-2);
    cout<<ave<<endl;
  }
  return 0;
}

Measured memory_bytes: 3144
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define rep2(i,n) for(int i = 1; i <= (n); ++i)
#define rrep2(i,n) for(int i = (n); i > 0; --i)
#define srep(i,s,n) for(int i = s; i < (n); ++i)
#define rsrep(i,s,n) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { int n = (__VA_ARGS__).size(); rep(i, n) printf("%d%s", (__VA_ARGS__)[i], i != n-1 ? " " : "\n"); }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;


int main() {
    ll n, a, b;
    cin >> n >> a >> b;

    ll sum = a+b;
    ll ans = 0;
    ans += n/sum * a;
    n -= n/sum * sum;
    ans += min(n, a);
    cout << ans << endl;
    return 0;
}

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

int main () {
  vector<int> line(3) ;
  
  for ( int i = 0 ; i < 3 ; i ++ ) {
    cin >> line.at(i) ;
  }
  
  sort (line.begin(),line.end()) ;
  
  cout << line.at(1) + line.at(0) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define rep(...) overload_rep(__VA_ARGS__, rep_1, rep_0) (__VA_ARGS__)
#define rep_0(i, end) for (int i = 0; i < (end); ++i)
#define rep_1(i, fr, ba) for (int i = (fr); i <= (ba); ++i)
#define overload_rep(arg_0, arg_1, arg_2, name, ...) name
#define all(box) box.begin(), box.end()
 
template <class T, class U> inline bool chmax(T& lhs, const U& rhs) { if (lhs < rhs) { lhs = rhs; return 1; } return 0; }
template <class T, class U> inline bool chmin(T& lhs, const U& rhs) { if (lhs > rhs) { lhs = rhs; return 1; } return 0; }

using dbl = long double;
constexpr dbl inf = 1e8;
constexpr dbl eps = 1e-10;

struct point {
  dbl x, y;
  point(dbl x = 0, dbl y = 0) : x(x), y(y) { }
};

struct line {
  dbl a, b, c;
  line(dbl a = 0, dbl b = 0, dbl c = 0) : a(a), b(b), c(c) { }
};

line vert(point p, point q) {
  dbl a = q.x - p.x, b = q.y - p.y;
  dbl x = (p.x + q.x) / 2.0L, y = (p.y + q.y) / 2.0L;
  dbl c = a * x + b * y;
  return line(a, b, c);
}

point inter(line l, line m) {
  if (std::abs(l.a) < eps) {
    if (std::abs(m.a) < eps) return point(inf, inf);
    dbl y = l.c / l.b;
    dbl x = (m.c - m.b * y) / m.a;
    return point(x, y);
  } else {
    dbl coeff = m.a / l.a;
    line n(l.a * coeff, l.b * coeff, l.c * coeff);
    if (std::abs(m.b - n.b) < eps) return point(inf, inf);
    dbl y = (m.c - n.c) / (m.b - n.b);
    dbl x = (l.c - l.b * y) / l.a;
    return point(x, y);
  }
}

int N;
point P[50];

bool ok(point c, dbl r) {
  rep (i, N) {
    dbl d = hypotl(P[i].x - c.x, P[i].y - c.y);
    if (d - r > eps) return false;
  }
  return true;
}

int main() {

  std::cin >> N;
  rep (i, N) std::cin >> P[i].x >> P[i].y;

  dbl ans = inf;
  rep (i, N) {
    rep (j, i) {
      {
        point center((P[i].x + P[j].x) / 2.0L, (P[i].y + P[j].y) / 2.0L);
        dbl radius = hypotl(P[i].x - P[j].x, P[i].y - P[j].y) / 2.0L;
        if (ok(center, radius)) chmin(ans, radius);
      }
      rep (k, j) {
        line l = vert(P[i], P[j]), m = vert(P[j], P[k]);
        point center = inter(l, m);
        if (abs(center.x - inf) < eps) continue;
        dbl radius = hypotl(P[i].x - center.x, P[i].y - center.y);
        if (ok(center, radius)) chmin(ans, radius);
      }
    }
  }

  std::cout << std::fixed << std::setprecision(30) << ans << '\n';
  return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric>
#include <set>
#include <cstdlib>
#include <queue>
#include <map>

using namespace std;

typedef long long llint;
typedef long double ld;
#define inf 1e18
#define mod 1000000007
priority_queue<llint,vector<llint>,greater<llint>> que;
//priority_queue<llint> q;

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

int n,a,b;
string s;

void solve(){
  cin >> n >> a >> b;
  cin >> s;
  int fr=1;
  int up=a+b;
  int c=0;
  for(int i=0;i<n;i++){
    if(s[i]=='c')cout << "No" << endl;
    else if(s[i]=='a'){
      if(c<up) {
        cout << "Yes" << endl;
        c++;
      }
      else cout <<  "No" << endl;
    }
    else{
      if(c<up){
        if(fr<=b){
          cout << "Yes" << endl;
          fr++;
          c++;
        }
        else cout << "No" << endl;
      }
      else cout << "No" << endl;
    }
  }
}

int main(int argc, char *argv[]) {
  solve();
  return 0;
}


Measured memory_bytes: 896
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include <numeric>
#include<map>
 
 
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 1e13
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
 
typedef long long int ll;
#define MOD 1000000007


/*nまでの素数を列挙して配列に保持*/
vector<ll> Eratosthenes(ll n,vector<ll>& arr){

	for(ll i = 0; i < n;i++){
		arr[i] = 1;
    }

	for(ll i = 2; i < sqrt(n); i++){
		if(arr[i]){
			for(ll j = 0; i * (j + 2) < n; j++){
				arr[i *(j + 2)] = 0;
			}
		}
    }
    vector<ll> prime;
    for(int i = 2;i < arr.size();i++){
        if(arr[i]){
            prime.push_back(i);
        }
    }
    return prime;
}


int main(){


    ll n;
    ll tmp = 1000000;
    vector<ll> arr(tmp+1);
    arr = Eratosthenes(tmp,arr);
    
    
    while(cin >> n,n){

        ll ans = 0;
        REP(i,n){
            ans += arr[i];
        }
        cout << ans << endl;        
    }
    
    
    return 0;
}


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

int main(){
  string s, t, u;
  int a, b;
  cin >> s >> t >> a >> b >> u;
  
  if(s == u) a--;
  if(t == u) b--;
  
  cout << a << " " << b << endl;
  
  
}

Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
#include <set>
#define isPowerOfTwo(S) (!(S & (S - 1)))
#define ll long long
#define ull unsigned long long
#define MAXN 1000000007
#define INF 1e12
using namespace std;
typedef pair<int,int> pi;
typedef pair<pi,int> trip;
typedef pair<ll int,ll int> pli;
typedef vector<int> vi;
typedef vector<ll int> vli;
typedef vector<vi> vvi;
string getString(char x)
{
    string s(1, x);

    return s;
}
int highestPowerof2(ll int n)
{if(n==0)
    return 0;
   int p = (int)log2(n);
   //cout<<p<<"highest"<<endl;
   return p;
}

int main()
{ios::sync_with_stdio(0);
	cin.tie(0);
    int test=1;
    //int cas=
    //cin>>test;
    vector<int>fact(1e6+1,0);
    for(int i=0;i<=1e6;i++)
        fact[i]=i;
    for(int i=2;i<=1e6;i++)
    {
        if(fact[i]==i)
        {
            for(int j=1;j*i<=1e6;j++)
                fact[j*i]=i;
        }
    }
    while(test--)
    {
       int n;
        cin>>n;
        vi vec(n);
        vi f(1e6+1,0);
        for(int i=0;i<n;i++)
        {cin>>vec[i];
         int k=vec[i];
         map<int,int>ma;
         //cout<<vec[i]<<" ";
         while(k>1)
         {
             int p=fact[k];
             //cout<<p<<" ";
             if(ma[p]==0)
             {ma[p]=1;f[p]++;}
             k/=p;
         }
         //cout<<endl;

        }
        int check=1;
        for(int i=0;i<f.size();i++)
        {
            if(f[i]>1)
                {check=0;}
        }
        if(check)
        {
            cout<<"pairwise coprime"<<endl;continue;
        }
        check=1;
        for(int i=0;i<f.size();i++)
        {
            if(f[i]>=n)
                {check=0;}
        }
        if(check)
        {
            cout<<"setwise coprime"<<endl;continue;
        }
        cout<<"not coprime"<<endl;

    }

}


Measured memory_bytes: 14972
#include<bits/stdc++.h>
#define ll long long

using namespace std;

int main(int argc, char const *argv[]) {

    ll n, k;
    cin>>n>>k;

    std::vector<ll> v(n);
    for (ll i = 0; i < n; i++) {
        cin>>v[i];
    }

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

    ll sum = 0;
    for(ll i=0;i<k;i++){
        sum += v[i];
    }

    std::cout << sum << '\n';
    return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <string>
using namespace std;
int main()
{
    int n;
    string s;
    cin >> n;
    cin >> s;
    int cnt = 0;
    for(int i = 0; i + 3 <= n; i ++)
    {
        if(s.substr(i, 3) == "ABC") cnt ++;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)(x.size())

const int N = 1e5 + 100;
int n, a[N];
signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);
    int ans1 = a[n - 1], nesf1 = ans1 / 2, nesf2 = (ans1 + 1) / 2, 
        ans2 = a[0], min_diff = a[n - 1] - a[0];
    for (int i = 1; i < n - 1; i++) {
        int diff = min(abs(a[i] - nesf1), abs(a[i] - nesf2));
        if (diff < min_diff) {
            min_diff = diff;
            ans2 = a[i];
        }
    }
    cout << ans1 << " " << ans2 << "\n";
}

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

int main(void)
{
    int n, m;
    
    cin >> n >> m;
    int cnt_n = (n==0) ? 0 : n * (n-1) / 2;
    int cnt_m = (m==0) ? 0 : m * (m-1) / 2;
    
    cout << cnt_n + cnt_m << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
using namespace std;

int main(){
    
    long long int X, K, D, rem, ans;
    cin >> X >> K >> D;
    
    X = abs(X);
    
    if (X / K >= D) {
        ans = X - K * D;

    } else if (K % 2 == 0){
        rem = X % (2 * D);
        ans = min(rem , 2 * D - rem);

    } else{
        rem = (X + D) % (2 * D);
        ans = min(rem, 2 * D - rem);

    }
        
    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 3644
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>


int main(void) {

	char taroCard[100] = { 0 };
	char hanakoCard[100] = { 0 };
	int taroResult = 0;
	int hanakoResult = 0;

	int n = 0;
	scanf("%d%*[^\n]%*c", &n);
	int i = 0;
	for (i =0; i < n; i++) {
		scanf("%s %s%*[^\n]%*c", &taroCard, &hanakoCard);

		int strlength = 0;
		strlength = strlen(taroCard);
		if (strlength < strlen(hanakoCard)) {
			strlength = strlen(hanakoCard);
		}

		int j = 0;
		for (j = 0; j < strlength; j++) { // 文字列は小文字のみ
			if (taroCard[j] != hanakoCard[j]) {
				if (taroCard[j] > hanakoCard[j]) {
					taroResult += 3;
				}
				else {
					hanakoResult += 3;
				}
				break;
			}
			else { // j文字目が等しいなら
				continue;
			}
		}
		if (strlength == j) {
			taroResult++;
			hanakoResult++;
		}
	}
	
	
	printf("%d %d\n", taroResult, hanakoResult);

	return 0;
}


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

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >>D;
  
  if (A + B > C + D)
    cout << "Left" << endl;
  
  else if (A + B < C + D)
    cout << "Right" << endl;
  
  else
    cout << "Balanced" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<string>
using namespace std;
typedef long long ll;
int main(){
  string N;
  int X=0;
  cin >> N;
  for(int i = 0; i < (int)N.size(); ++i){
    int a = N[i] - '0';
    X += a;
  }
  if(X%9==0){
    cout << "Yes";
  }else{
    cout << "No";
  }
}


Measured memory_bytes: 3720
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

n = int(input())
a = list(map(int, input().split()))
a.sort()
if n == 2:
    print(max(a))
else:
    a1 = gcd(a[0],a[1])
    a2 = gcd(a[1],a[2])
    a3 = gcd(a[2],a[0])
    m = max(a1,a2,a3)
    judge = 0
    for i in range(m):
        if judge == 1:
            break
        cnt = 0
        for j in range(n):
            if a[j] % (m-i) != 0:
                cnt += 1
            if cnt > 1:
                break
            if j == n-1 and cnt <= 1:
                print(m-i)
                judge = 1

Measured memory_bytes: 14488
unittest
{
	assert( [ "axyb", "abyxb" ].parse.expand.solve == "axb" );
	assert( [ "aa", "xayaz" ].parse.expand.solve == "aa" );
	assert( [ "a", "z" ].parse.expand.solve == "" );
	assert( [ "abracadabra", "avadakedavra" ].parse.expand.solve == "aaadara" );
}



import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto s = input.front;
	input.popFront;
	auto t = input.front;
	return tuple( s, t );
}

auto solve( string s, string t )
{
	// dp[ si ][ ti ] = s[ 0 .. si ]とt[ 0 .. ti ]の最長共通部分列の長さ
	auto dp = new long[][]( 1 + s.length, 1 + t.length );
	for( auto si = 0L; si < s.length; si++ )
	{
		for( auto ti = 0L; ti < t.length; ti++ )
		{
			if( s[ si ] == t[ ti ] )
			{
				// 文字が一致する場合、長さを+1する
				dp[ si + 1 ][ ti + 1 ] = dp[ si ][ ti ] + 1;
			}
			else
			{
				// 文字が一致しない場合、一つ前の長いほうを使う
				dp[ si + 1 ][ ti + 1 ] = max( dp[ si ][ ti + 1 ], dp[ si + 1 ][ ti ] );
			}
		}
	}
	
	// dpを逆に辿って共通部分列を復元
	auto ans = "";
	auto si = s.length;
	auto ti = t.length;
	while( 0 < si && 0 < ti )
	{
		if( dp[ si ][ ti ] == dp[ si - 1 ][ ti ] )
		{
			si--;
			continue;
		}
		
		if( dp[ si ][ ti ] == dp[ si ][ ti - 1 ] )
		{
			ti--;
			continue;
		}
		
		si--;
		ti--;
		ans = s[ si ] ~ ans;
	}
	
	return ans;
}


Measured memory_bytes: 78076
a, b, k = map(int, input().split(" "))

for i in range(k):
    if i == 0:
        ans = [a + i]
    else:
        if a + i <= b:
            ans.append(a + i)
        else:
            break
            
for i in range(k):
    p = b - (k - 1) + i
    if p < a:
        break
    
    elif p not in ans:
        ans.append(p)
        
    else:
        continue


for i in range(len(ans)):
    print(ans[i])

Measured memory_bytes: 3064
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<cctype>
#include<string.h>
#include <stdlib.h>

#define PI 3.1415926
void swap(int* x, int* y) {
	int a = *x;
	int b = *y;
	*x = b;
	*y = a;
}
int factorial(int n);
int sum(int n, int*);
int ave(int n, int*);
int min(int n, int*), min(int n, int m);
int max(int n, int*), max(int n, int m);

int main() {
	int p1, p2, p3, j1, j2;
	scanf("%d %d %d %d %d", &p1, &p2, &p3, &j1, &j2);
	printf("%d\n", min(min(p1, p2), p3) + min(j1, j2) - 50);
	return 0;
}

int factorial(int n) {
	if (n > 0) {
		return n * factorial(n - 1);
	}
	else {
		return 1;
	}
}
int sum(int n, int *all) {
	int total = 0;
	for (int i = 0; i < n; ++i) {
		total += all[i];
	}
	return total;
}
int ave(int n, int *all) {
	int total = 0;
	for (int i = 0; i<n; ++i) {
		total += all[i];
	}
	return total / n;
}
int min(int n, int *all) {

	int min = all[0];
	for (int i = 1; i < n; ++i) {
		if (all[0] > all[i]) {
			min = all[i];
		}
	}
	return min;
}
int max(int n, int *all) {
	int max = all[0];
	for (int i = 1; i<n; ++i) {
		if (all[0]<all[i]) {
			max = all[i];
		}
	}
	return max;
}
int max(int n, int m) {
	if (n >= m) {
		return n;
	}
	else {
		return m;
	}
}
int min(int n, int m) {
	if (n >= m) {
		return m;
	}
	else {
		return n;
	}
}

Measured memory_bytes: 2676
import java.util.Scanner;
public class Main {
	public static boolean acgt(char c) {
		if(c == 'A' || c == 'C' || c == 'G' || c == 'T') {
			return true;
		}
		return false;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] s = sc.next().toCharArray();
		int cnt = 0;
		int tmp = 0;
		for(char i:s) {
			if(acgt(i)) {
				cnt++;
				if(tmp < cnt)tmp = cnt;
			}else {
				cnt = 0;
			}
		}
		System.out.println(tmp);
		sc.close();
	}
}


Measured memory_bytes: 21844
#include <cstdio>
#include <cstdlib>

int main(){
    int N, Q;
    scanf("%d %d", &N, &Q);
    char* S;
    S = new char[N+1];
    scanf("%s", S);
    int* s;
    s = new int[N];
    int count = 0;
    for(int i=0; i<N; i++){
        if(S[i-1]=='A' && S[i]=='C'){
            count++;
        }
        s[i] = count;
    }
    int l, r;
    for(int i=1; i<=Q; i++){
        scanf("%d %d", &l, &r);
        printf("%d\n", s[r-1] - s[l-1]);
    }
    delete[] s;
    delete[] S;
    return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
#include <bitset>
#include <cassert>
#include <cstring>
#include <functional>
#include <iomanip>
#include <list>
#include <cmath>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <vector>
// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
using namespace std;
#define REP(i, n) for (int64_t i = 0; i < (int64_t)n; i++)
#define REP_FOR(i, a, b) for (int64_t i = (int64_t)a; i < (int64_t)b; i++)
#define REP_REV(i, a, b) for (int64_t i = (int64_t)a; i > (int64_t)b; i--)
#define FORALL(v) (v).begin(), (v).end()
#define mp(a, b) make_pair(a, b)
#define eb(x) emplace_back(x)
#define F first
#define S second
typedef long long ll;
typedef long double ld;
typedef pair<int64_t, int64_t> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int64_t> vii;
typedef vector<vii> vvii;
const ll mod = 1e9 + 7;
const int64_t infi = 1147483600;
const ll infl = 4e18 + 5;
const char EOL = '\n';
// const ll MOD = 1000000009;
//cout << fixed << setprecision(17) << res << endl;

#define M 1000000007

int main() {
    ll n;
    cin >> n;
    map<ll, map<ll,ll>> E;
    for (ll i = 0; i < n; ++i) {
        ll v, u, d;
        cin >> v >> u >> d;
        if (E.find(v) == E.end()) {
            E[v] = map<ll,ll>();
        }
        E[v].insert(make_pair(u, d));
        if (E.find(u) == E.end()) {
            E[u] = map<ll,ll>();
        }
        E[u].insert(make_pair(v, d));
    }
    set<ll> checked, even, odd;
    queue<ll> q;
    q.push(1);
    even.insert(1);
    while (!q.empty()) {
        ll cur = q.front(); q.pop();
        checked.insert(cur);
        bool isEven = even.find(cur) != even.end();
        for (auto & e : E[cur]) {
            if (checked.find(e.first) != checked.end()) continue;
            if ((isEven && (e.second % 2) == 0) || (!isEven && (e.second % 2 != 0))) {
                even.insert(e.first);
            } else {
                odd.insert(e.first);
            }
            q.push(e.first);
        }
    }
    for (ll i = 1; i <= n; ++i) {
        if (even.find(i) != even.end()) {
            cout << 0 << endl;
        } else {
            cout << 1 << endl;
        }
    }

}


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

int main(){
  int m,d,count=0;
  cin>>m>>d;
  if(d<22||m<4){
    cout<<0<<endl;
    return 0;
  }
  for(int j=4;j<=m;j++){
  for(int i=22;i<=d;i++){
    int d1=i%10,d10=i/10;
    if(d1<2) continue;
    else if(d1*d10==j) count++;
  }
  }
  cout<<count<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>

using namespace std;

#define REP(i,n) for(int i=0;i<int(n);i++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
typedef long long ll;
typedef pair<int,int> P;


vector<int> b[110];

int main(void){
	          int i,j,k;

	          int h,w,n;
	          cin >> h >> w >> n;
	          queue<int> a;
	          for(i=1;i<=n;i++){
	        	  int x;
	        	  cin >> x;
	        	  for(j=1;j<=x;j++){
	        	       a.push(i);
	        	  }
	          }


	        	  for(j=0;j<h;j++){
	        		  if(j%2==0){
	        			  for(k=0;k<w;k++){
	        				  int d=a.front();
	        				  a.pop();
	        				  b[j].push_back(d);
	        			  }
	        		  }else{
	        			  for(k=w-1;k>=0;k--){
	        				  int d=a.front();
	        				  a.pop();
	        				  b[j].push_back(d);
	        		  }
	        			  reverse(b[j].begin(),b[j].end());
	        	  }
	        	  }

	        		  for(j=0;j<h;j++){
	        			  for(k=0;k<w;k++){
	        				 if(k!=w-1) cout << b[j][k] << ' ';
	        				 else cout << b[j][k] << endl;
	        			  }
	        		  }


	          return 0;
}


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

#define rep_(v, f, l) for (int v = (f), v##_ = (l); v < v##_; ++v)
#define rep(v, n) rep_(v, 0, n)
#define lep(v, n) rep_(v, 1, n + 1)
#define rrep_(v, f, l) for (int v = (l), v##_ = (f); v >= v##_; --v)
#define rrep(v, n) rrep_(v, 0, n - 1)
#define rlep(v, n) rrep_(v, 1, n)
#define show_a(a, size) rep(a##_it, size) std::cout << a[a##_it] << " \n"[a##_it == a##_it_ - 1];
#define show_v(v) show_a(v, v.size())
#define eachv(v, i) rep(i, v.size())
#define reachv(v, i) rrep(i, v.size())
#define debug(x) std::cerr << #x << " = " << x << "\n";

using namespace std;

typedef long long int lint;

static inline int in(){ int x; scanf("%d", &x); return x; }
static inline lint inl(){ lint x; scanf("%lld", &x); return x; }

int main()
{
    int pasta = min(in(), min(in(), in()));
    int juice = min(in(), in());
    printf("%d\n", pasta + juice - 50);
    return (0);
}

Measured memory_bytes: 1188
/*
このコード、と～おれ!
Be accepted!
∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
 　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
		  　　　　　　　　　　(¸.·´ (¸.·'* ☆
					*/

#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <numeric>
#include <iostream>
#include <random>
#include <map>
#include <unordered_map>
#include <queue>
#include <regex>
#include <functional>
#include <complex>
#include <list>
#include <cassert>
#include <iomanip>
#include <set>
/*多倍長整数/cpp_intで宣言
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
*/

//#pragma gcc target ("avx2")
//#pragma gcc optimization ("o3")
//#pragma gcc optimization ("unroll-loops")
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, n) for(int i = 1; i <= (n); ++i)
#define rep2(i, n) for(int i = 2; i < (n); ++i)
#define repr(i, n) for(int i = n; i >= 0; --i)
#define reprm(i, n) for(int i = n - 1; i >= 0; --i)
#define printynl(a) printf(a ? "yes\n" : "no\n")
#define printyn(a) printf(a ? "Yes\n" : "No\n")
#define printYN(a) printf(a ? "YES\n" : "NO\n")
#define printim(a) printf(a ? "possible\n" : "imposible\n")
#define printdb(a) printf("%.50lf\n", a)//少数出力
#define printdbd(a) printf("%.16lf\n", a)//少数出力(桁少なめ)
#define prints(s) printf("%s\n", s.c_str())//string出力
#define all(x) (x).begin(), (x).end()
#define allsum(a, b, c) ((a + b) * c / 2)//等差数列の和、初項,末項,項数
#define pb push_back
#define priq priority_queue
#define rpriq priq<int, vector<int>, greater<int>>
#define deg_to_rad(deg) (((deg)/360.0)*2.0*PI)
#define rad_to_deg(rad) (((rad)/2.0/PI)*360.0)
#define Please return
#define AC 0
#define addf(T) [](T a, T b){return (a + b);}
#define minf(T) [](T a, T b){return min(a, b);}
#define maxf(T) [](T a, T b){return max(a, b);}


using ll = long long;

constexpr int INF = 1073741823;
constexpr int MINF = -1073741823;
constexpr ll LINF = ll(4661686018427387903);
constexpr ll MOD = 1000000007;
const long double PI = acos(-1.0L);

using namespace std;

void scans(string& str) {
	char c;
	str = "";
	scanf("%c", &c);
	if (c == '\n')scanf("%c", &c);
	while (c != '\n' && c != -1) {
		str += c;
		scanf("%c", &c);
	}
}

void scanc(char& str) {
	char c;
	scanf("%c", &c);
	if (c == -1)return;
	while (c == '\n') {
		scanf("%c", &c);
	}
	str = c;
}

double acot(double x) {
	return PI / 2 - atan(x);
}

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

ll lcm(ll number1, ll number2) {
	return number1 / gcd(number1, number2) * number2;
}

ll LSB(ll n) { return (n & (-n)); }

/*-----------------------------------------ここからコード-----------------------------------------*/



int main() {

	int n, k;
	scanf("%d%d", &n, &k);
	vector<int> a(n);
	int g = 1;
	rep(i, n) {
		scanf("%d", &a[i]);
		if (i == 0)g = a[i];
		else g = gcd(a[i], g);
	}
	sort(all(a));
	printf("%s\n", (k% g == 0 && a[n - 1] >= k) ? "POSSIBLE" : "IMPOSSIBLE");

	Please AC;
}


Measured memory_bytes: 640
N = gets.to_i
A = gets.split.map(&:to_i)

H = A.tally
H.default = 0
sum = A.sum

puts gets.to_i.times.map{
	b,c = gets.split.map(&:to_i)
	n = H[b]
	H[b] = 0
	H[c] += n
	sum += (c-b)*n
}


Measured memory_bytes: 25816
n = gets.chomp
arr = n.to_s.chars

hon = ["2","4","5","7","9"]
pon = ["0","1","6","8"]
bon = ["3"]

if hon.include?(arr[-1])
  print "hon"
elsif pon.include?(arr[-1])
  print "pon"
elsif bon.include?(arr[-1])
  print "bon"
end



Measured memory_bytes: 14280
#include <cstdio>
using namespace std;

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

int main()
{
	int xy[10][10] = {0};
	int x,y,size;
	
	while(scanf("%d,%d,%d", &x,&y,&size) != EOF){
		if (size < 4){
			for (int d = 0; d < 1 + size * 4; d++){
				int nx, ny;
				nx = x + dx[d];
				ny = y + dy[d];
				if (nx >= 0 && nx < 10 && ny >= 0 && ny < 10){
					xy[nx][ny] += 1;
				}
			}
		}
	}
	int w=0,con = 0;
	
	for(int i=0; i < 10; i++){
		for(int j=0; j < 10; j++){
			if(xy[i][j] == 0)w++;
			if(con < xy[i][j])con = xy[i][j];
		}
	}
	
	printf("%d\n%d\n", w, con);

	return (0);
}

Measured memory_bytes: 1028
#include <bits/stdc++.h>
#define NONE 0
#define BLACK 1
#define WHITE 2
using namespace std;

int d[] = {-1, 0, 1};
int v[10][10][10];
int n, m, p;

bool infield(int x, int y, int z){
  return 0 <= x && x < n && 0 <= y && y < n && 0 <= z && z < n;
}

int check(){
  int beginx, beginy, beginz;
  int dx, dy, dz;
  for(int z = 0; z < n; z++){
    for(int y = 0; y < n; y++){
      for(int x = 0; x < n; x++){
        for(int a = 0; a < 3; a++){
          for(int b = 0; b < 3; b++){
            for(int c = 0; c < 3; c++){
              if(a == 1 && b == 1 && c == 1) continue;
              int color = v[z][y][x];
              if(color == 0) continue;
              beginx = x; beginy = y; beginz = z;
              dx = d[a]; dy = d[b]; dz = d[c];
              int cnt = 0;
              //cout << "--" << endl;
              while(infield(beginx, beginy, beginz)){
                if(v[beginz][beginy][beginx] != color){break;}
                beginx += dx; beginy += dy; beginz += dz;
                cnt++;

                //cout << v[beginz][beginy][beginz] << " " << color << endl;

              }

              if(cnt >= m) return color;
            }
          }
        }
      }
    }
  }
  return 0;
}

int main(void){
  ios::sync_with_stdio(false);
  cin.tie(0);
  while(cin >> n >> m >> p, n | m | p){
    for(int i = 0; i < 10; i++) for(int j = 0; j < 10; j++) for(int k = 0; k < 10; k++) v[i][j][k] = 0;
    int flg = 0;
    for(int i = 0; i < p; i++){
      int x, y; cin >> x >> y;
      x--; y--;
      for(int z = 0; z < 10; z++){
        if(v[z][y][x] == 0){
          v[z][y][x] = i%2 + 1;
          break;
        }
      }

      /*
         for(int f = 0; f < 3; f++){
         for(int g = 0; g < n; g++){
         for(int h = 0; h < n; h++){
         cout << v[f][g][h];
         }
         cout << endl;
         }
         cout << endl;
         }
         cout << endl;
         */

      if(flg == 0){
        flg = check();
        if(flg == WHITE){
          cout << "White" << " " << i+1 << endl;
        }else if(flg == BLACK){
          cout << "Black" << " " << i+1 << endl;
        }
      }
    }
    if(flg == 0){
      cout << "Draw" << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 3104
#include <algorithm>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <map>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const int inf = 1 << 30;
const int INF = INT_MAX;

vector<pair<int, int>> v[100010];
int p[100010];
int y[100010];
char id[100010][15];

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    cin >> p[i] >> y[i];
    v[p[i] - 1].push_back(make_pair(y[i], i));
  }
  for (int i = 0; i < n; ++i) {
    sort(v[i].begin(), v[i].end());
    for (int j = 0; j < v[i].size(); ++j) {
      int k = v[i][j].second;
      sprintf(id[k], "%06d%06d", i + 1, j + 1);
    }
  }
  for (int i = 0; i < m; ++i) {
    cout << id[i] << endl;
  }
  return 0;
}

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

int main(){
	int n;
	cin >> n;
	int number[n];
  int count[n] = {0};
	for(int i=1;i<n;i++){
    scanf("%d",&number[i]);
  }
  for(int i=1;i<n;i++){
    count[number[i]-1]++;
  }
  rep(i,n)printf("%d\n",count[i]);

}

Measured memory_bytes: 5324
n=int(input())
a=[0]
vis=[0]*(n+1)
for _ in range(n):
    x=int(input())
    a.append(x)
ans=0
cur=1
while vis[cur]==0:
    #print(cur,end=' cur\n')
    vis[cur]=1
    if cur==2:
        break
    ans+=1
    cur=a[cur]
if vis[2]==0:
    print('-1')
else:
    print(ans)
    


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

int main() {
  int s, a, b, c;
  cin >> s;
  a = s % 10;
  s = s / 10;
  b = s % 10;
  s = s / 10;
  c = s % 10;
  cout << a+b+c <<endl;
}

Measured memory_bytes: 256
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N, M = map(int, input().split())
    if N & 1:
        for i in range(1, M+1):
            print(i, N - i)
    else:
        flg = 1
        for i in range(1, M+1):
            if flg:
                a = i
                b = N + 1 - i
                if b - a <= N - (b-a):
                    flg = 0
                    b -= 1
                print(a, b)
            else:
                print(i, N-i)


if __name__ == '__main__':
    main()


Measured memory_bytes: 70072
// #include <bits/stdc++.h>
#include <iostream>
#include <map>
#include <cmath>
#include <ios>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <stack>
#include <numeric>
// #include <windows.h>
using namespace std;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;
template<class T> using VVV = V<VV<T>>;
template<class T1, class T2> using P = pair<T1, T2>;
using I = int;
using D = double;
using B = bool;
using C = char;
using S = string;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = P<I, I>;
using VPII = V<PII>;
using PLL = P<LL, LL>;
using VPLL = V<PLL>;
using VI = V<I>;
using VVI = VV<I>;
using VLL = V<LL>;
using VVLL = VV<LL>;
using VC = V<C>;
using VVC = VV<C>;
using VS = V<S>;
using VVS = VV<S>;
using VB = V<B>;
using VVB = VV<B>;
#define REP(type, i, n) for (type i = 0; i < (type)(n); ++i)
#define REP2(type, i, m, n) for (type i = (m); i < (type)(n); ++i)
#define REPR(type, i, n) for (type i = (n)-1; i >= 0; --i)
#define REPR2(type, i, m, n) for (type i = (n)-1; i >= (m); --i)
#define REPx(x, a) for(auto x : a)
#define ALL(a) a.begin(), a.end()
#define SORT(a) sort(ALL(a))
#define SORTR(a, type) sort(ALL(a), greater<type>())
#define SORTF(a, comp) sort(ALL(a), comp)
#define REVERSE(a) reverse(ALL(a))
#define SIZE(a, type) ((type)(a).size())
#define bit_search(bit, n) REP(LL, bit, 1LL<<(n))
#define bit_check(bit, i) ((bit>>(i)) & 1)
#define setpre(n) fixed << setprecision((n))
#define UNIQUE(a) do {SORT(a); (a).erase(unique(ALL(a)), (a).end());} while(0)
#define MAX(a) *max_element(ALL(a))
#define MIN(a) *min_element(ALL(a))
#define bisect_left(a, x) (lower_bound(ALL(a), (x)) - a.begin())
#define bisect_right(a, x) (upper_bound(ALL(a), (x)) - a.begin())
#define INPUT(a) REPx(&x, a) cin >> x;
#define INPUT2(a) REPx(&x, a) INPUT(x);
#define INPUTP(a) REPx(&x, a) cin >> x.first >> x.second;
#define ENDL cout << endl;

// const int INF = 2e9;
const LL INF = 9e18;
const LL MOD = 1e9+7;

template<class T> using PRIORITY_QUEUE = priority_queue< T, V<T>, greater<T> >;
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;}
template<class T> inline void debug1(V<T> A){REP(int, i, SIZE(A, int)){if (A[i] == INF) cout << "I ";else cout << A[i] << " ";}ENDL}
template<class T> inline void debug2(VV<T> A){REP(int, i, SIZE(A, int)){REP(int, j, SIZE(A[i], int)){if (A[i][j] == INF) cout << "I "; else cout << A[i][j] << " ";}ENDL}}


int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, k, head, tail;
  cin >> n >> k;
  VI A(n);
  INPUT(A);
  REP(int, i, n)
  {
    if (i < k) continue;
    head = A[i-k];
    tail = A[i];
    if (tail > head) cout << "Yes" << endl;
    else cout << "No" << endl;
  }

  return 0;
}


Measured memory_bytes: 3988
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#define endl "\n"
#define INF 999999999
#define ll long long int
using namespace std;

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

    vector < pair <ll, ll> > spells(n);

    ll i, j;
    for(i = 0; i < n; i ++)
    {
    	cin >> spells[i].first >> spells[i].second;
    }

    vector <ll> dp(h + 1, INF);
	dp[0] = 0;
	for(i = 1; i <= h; i ++)
	{
		for(j = 0; j < n; j ++)
		{
			ll val = i - spells[j].first;
			if(val < 0)
				val = 0;
			if(dp[val] + spells[j].second <= dp[i])
				dp[i] = dp[val] + spells[j].second;
		}
	}    

	// for(i = 0; i <= h; i ++)
	// 	cout << dp[i] << " ";
	// cout << endl;
	cout << dp[h] << endl;
}

Measured memory_bytes: 384
#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

use itertools::Itertools;
use proconio::*;
use std::collections::VecDeque;
use std::io::stdin;
use std::str::FromStr;
use text_io::*;

const U_INF: usize = 1 << 60;
const I_INF: isize = 1 << 60;

fn main() {
    let mut sc = Scanner::new();
    let n = sc.next_usize();
    let mut n = n;
    let mut s = String::new();

    while n != 0 {
        let a = n / 26;
        let b = (n % 26) as u8;
        n = a;
        // eprintln!("{:?}", (a, b));
        let b = if b == 0 {
            n -= 1;
            25
        } else {
            b - 1
        };
        s.push((b'a' + b) as char);
    }

    println!("{}", s.chars().rev().collect::<String>());
}

pub struct Scanner {
    buf: VecDeque<String>,
}

impl Scanner {
    pub fn new() -> Self {
        Self {
            buf: VecDeque::new(),
        }
    }

    fn scan_line(&mut self) {
        let mut flag = 0;
        while self.buf.is_empty() {
            let mut s = String::new();
            stdin().read_line(&mut s).unwrap();
            let mut iter = s.split_whitespace().peekable();
            if iter.peek().is_none() {
                if flag >= 5 {
                    panic!("There is no input!");
                }
                flag += 1;
                continue;
            }

            for si in iter {
                self.buf.push_back(si.to_string());
            }
        }
    }

    pub fn next<T: FromStr>(&mut self) -> T {
        self.scan_line();
        self.buf
            .pop_front()
            .unwrap()
            .parse()
            .unwrap_or_else(|_| panic!("Couldn't parse!"))
    }

    pub fn next_usize(&mut self) -> usize {
        self.next()
    }

    pub fn next_isize(&mut self) -> isize {
        self.next()
    }

    pub fn next_chars(&mut self) -> Vec<char> {
        self.next::<String>().chars().collect_vec()
    }

    pub fn next_string(&mut self) -> String {
        self.next()
    }

    pub fn fill_vec_line<T: FromStr>(&mut self, v: &mut Vec<T>) {
        for vi in v {
            *vi = self.next();
        }
    }

    pub fn fill_vec<T: FromStr>(&mut self, v: &mut Vec<Vec<T>>) {
        for vi in v {
            for vii in vi {
                *vii = self.next();
            }
        }
    }

    pub fn make_vec_line<T: FromStr + Default + Clone>(&mut self, i: usize) -> Vec<T> {
        let mut v = vec![Default::default(); i];
        self.fill_vec_line(&mut v);
        v
    }

    pub fn make_vec<T: FromStr + Default + Clone>(&mut self, i: usize, j: usize) -> Vec<Vec<T>> {
        let mut v = vec![vec![Default::default(); j]; i];
        self.fill_vec(&mut v);
        v
    }
}


Measured memory_bytes: 2108
#include <bits/stdc++.h>
        using namespace std;
   #define int long long
const int MAX = 510000;
const int MOD = 1000000007;
//



     signed main(){
  int d;
  clock_t st=clock();
  cin>>d;
    clock_t ed=clock();

  int c[26];
  for(int i=0;i<26;i++)cin>>c[i];
  int t[d],s[d][26],x[26]={};
    vector<int>v[26];
    for(int i=0;i<26;i++)v[i].push_back(-1);

  for(int i=0;i<d;i++)for(int j=0;j<26;j++)cin>>s[i][j];
   // cerr<<'i';
  for(int i=0;i<d;i++){
      for(int j=0;j<26;j++)x[j]+=c[j];
      int k=0;
      for(int j=1;j<26;j++)if(x[k]+s[i][k]<x[j]+s[i][j])k=j;
      t[i]=k;
      x[k]=0;
      v[k].push_back(i);
  }
  for(int i=0;i<26;i++)v[i].push_back(d);
//for(int i=0;i<d;i++)cout<<t[i]+1<<endl;
  // cerr<<double(clock()-st)/CLOCKS_PER_SEC<<endl;
//while(false){
while(double(clock()-st)/CLOCKS_PER_SEC<1.95){
  if(rand()%100){
    int p=rand()%d;
    auto q=find(v[t[p]].begin(),v[t[p]].end(),p);
    q++;
  // int m=(p+(*q))/2;
   int m=p+rand()%((*q)-p);
//cerr<<m<<' '<<p<<endl;
   if(m==p)continue;
   auto r1=find(v[t[m]].begin(),v[t[m]].end(),m);
   auto r0=r1-1,r2=r1+1;
   if((m-p)*((*q)-m)*c[t[p]]+s[m][t[p]]>(m-(*r0))*((*r2)-m)*c[t[m]]+s[m][t[m]]){
 
    v[t[p]].insert(q,m);
    v[t[m]].erase(r1);
    t[m]=t[p];
   }
  }else{
    int u=1;
    //if(rand()%2)u++;
    if(u>=d)continue;
    int p=rand()%(d-u);
    if(t[p]==t[p+u]||p+u==d){continue;}
    auto q1=find(v[t[p]].begin(),v[t[p]].end(),p);
    auto q0=q1-1,q2=q1+1;
      auto r1=find(v[t[p+u]].begin(),v[t[p+u]].end(),p+u);
    auto r0=r1-1,r2=r1+1;
    if((p-(*q0))*((*q2)-p)*c[t[p]]+s[p][t[p]]+(p+u-(*r0))*((*r2)-p-u)*c[t[p+u]]+s[p+u][t[p+u]]<(p+u-(*q0))*((*q2)-p-u)*c[t[p]]+s[p+u][t[p]]+(p-(*r0))*((*r2)-p)*c[t[p+u]]+s[p][t[p+u]]){
      (*q1)=p+u;
      (*r1)=p;
      swap(t[p],t[p+u]);
    }
   
  }




}
     for(int i=0;i<d;i++)cout<<t[i]+1<<endl;


     }


 


 






    





      

        


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

using namespace std;

int main(){
  int h, w, cnt = 0;
  string line;
  cin >> h >> w;
  for(int i = 0; i < h; i++){
    cin >> line;
    for(int j = 0; j < w; j++) if(line[j] == '#') cnt++;
  }
  cout << (h + w - 1 - cnt ? "Impossible" : "Possible") << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define SZ(x) ((int)(x).size())
#define rep(i,n) for(int i=0;i<(n);++i)
#define fore(i,a) for(auto &i:a)
#define Yes cout << "Yes" << endl;
#define No cout << "No" << endl;
#define answer cout << ans << endl;
signed _main(); signed main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
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; }
template<class T> using v = vector<T>;
template<class T> using vv = vector<v<T>>;
const int MOD=1e9+7;
const long long INF = 1LL << 60;
using P=pair<double,double>;

signed _main(){
  // 入力
  int n; // 都市数
  cin >> n;

  P field[n];
  rep(i,n){
    cin >> field[i].first >> field[i].second;
  }

  vector<vector<double> > dist(n, vector<double>(n)); // 各都市間の所要時間
  for (int i = 0; i < n; ++i) {
    for (int j = i+1; j < n; ++j) {
      double d=sqrt((field[i].first-field[j].first)*(field[i].first-field[j].first)+(field[i].second-field[j].second)*(field[i].second-field[j].second));
      dist[i][j]=d;
      dist[j][i]=d;
    }
  }
  // 初期順列
  vector<int> order(n);
  for (int i = 0; i < n; ++i) order[i] = i;

  // 探索
  double sum = 0,N=0;
  do {
    N++;
    for (int i = 1; i < n; ++i) {
      sum += dist[order[i-1]][order[i]];
    }
  } while (next_permutation(order.begin(), order.end()));

  // 答えを出力
  cout << fixed << setprecision(6) << sum/N << endl;
}


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

int main() {
  int n, k, sum = 0;
  cin >> n >> k;

  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];

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

  for (int i = 0; i < k; i++) sum += a[i];

  cout << sum << endl;
}

Measured memory_bytes: 3628
// 

#include <vector>
#include <iostream>
#include <queue>
#include <climits>
using namespace std;

#define INF 2000
#define F first
#define S second
typedef pair< int, int > ii;

const int N = 10;

int n, start, finish;
int cost[N][N]; // adjacency matrix
int freq[10]; // number of each digit on the wall

priority_queue< ii, vector< ii >, greater< ii > > pq;

int dist[N];
bool visit[N];

int row, col;

void input ()
{
	cin >> row >> col;
	
	for (int i = 0; i < 10; ++i) 
	for (int j = 0; j < 10; ++j) cin >> cost[j][i]; // reversed
	
	int digit;
	for (int i = 1; i <= row; ++i)
	for (int j = 1; j <= col; ++j) {
		cin >> digit;
		if (digit != -1) ++freq[digit];
	}
}

void init ()
{
	for (int i = 0; i < 10; ++i) dist[i] = INF;
	dist[1] = 0;
	pq.emplace(0, 1);
}

void dijkstra ()
{
	input();
	init();
	
	int proc;
	while (!pq.empty())
	{
		proc = pq.top().second;
		pq.pop();
		
		if (visit[proc]) continue;
		visit[proc] = true;
		
		int temp;
		int adj;
		for (int i = 0; i < 10; ++i) {
			
			adj = i;
			temp = cost[proc][i] + dist[proc];
			
			if (temp < dist[adj]) {
				dist[adj] = temp;
				pq.emplace(temp, adj);
			}
		}
	}
	
	long long ans = 0;
	for (int i = 0; i < 10; ++i) {
		ans += (long long) dist[i]*freq[i];
	}
	
	cout << ans << "\n";
	
	return;
}

int main ()
{
	dijkstra();
	return 0;
}

Measured memory_bytes: 256