akhauriyash/Code-Regression huggingface dataset:
sx,sy,tx,ty=map(int,input().split())

iki=["U" for i in range(ty-sy)]+["R" for i in range(tx-sx)]
kaeri=["D" for i in range(ty-sy)]+["L" for i in range(tx-sx)]
iki2=["L"]+["U" for i in range(ty-sy+1)]+["R" for i in range(tx-sx+1)]+["D"]
kaeri2=["R"]+["D" for i in range(ty-sy+1)]+["L" for i in range(tx-sx+1)]+["U"]
ans=iki+kaeri+iki2+kaeri2
print(*ans,sep="")

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

int main(){
  int n,x,y;
  cin>>n>>x>>y;
  x--; y--;
  vector<int> ans(n,0);
  for(int i = 0; i < n; i++){
    for(int j = i+1; j < n; j++){
      ans[min(j-i,abs(i-x)+abs(j-y)+1)]++;
    }
  }
  rep(i,n-1){
    cout<<ans[i+1]<<endl;
  }
}


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

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

using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second　//pairの二つ目の要素


int main(){
   int n;
   cin>>n;
   ll x[n];
   ll minv=1000, maxv=0;
   REP(i,n){
      cin>>x[i];
      if(x[i]<minv) minv=x[i];
      if(x[i]>maxv) maxv=x[i];
   }
   int p;
   ll ans=INF;
   for(p=minv;p<=maxv;p++){
      ll a=0;
      REP(i,n) a+=(x[i]-p)*(x[i]-p);
      ans=min(ans,a);
   }

   cout<<ans<<endl;
   return 0;
}

Measured memory_bytes: 256
#prepare
L = []
Q = []

#input
W, H, N, = map(int,raw_input().split())
for i in range(N):
    L.append(map(int,raw_input().split()))
x1=0
x2=W
y1=0
y2=H

#calculate
Q = [row[2] for row in L]


for k in range(N):
    if Q[k] == 1:
        x1 = max(x1,L[k][0])
    elif Q[k] == 2:
        x2 = min(x2,L[k][0])
    elif Q[k] == 3:
        y1 = max(y1,L[k][1])
    elif Q[k] == 4:
        y2 = min(y2,L[k][1])

print max(0,x2-x1) * max(0,y2-y1)


Measured memory_bytes: 2696
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <functional>
#include <random>
#include <string>
#include <stack>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>

using std::cin;
using std::cout;
using std::cerr;
using std::endl;

using ll = long long;

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

  std::string s;

  cin >> s;

  int s_num = 0, ans = s.size();

  for (int i = 0; i < s.size(); ++i) {
    if (s[i] == 'S') {
      s_num++;
    }
    else {
      if (s_num > 0) {
        s_num--;
        ans -= 2;
      }
    }
  }

  cout << ans << endl;
  
  return 0;
}

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

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

	int ans = 1;
	for (int i = 0; i < n; i++) {
		if (ans < k) ans *= 2;
		else ans += k;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct conv { 
	int l, r, x, pa;
       	bool can_merge(conv oth){
		if(r + 1 == oth.l){
			if(pa != oth.pa) return false;
			if(pa){
				if(x + r + 1 == oth.x + l) return true;
			} else {
				if(x == oth.x) return true;
			}
		}
		return false;
	}	
	conv operator + (conv oth){
		assert(can_merge(oth));
		return {l, oth.r, x, pa};
	}
};
struct node {
	vector<conv> convs;
	int get_id(int x){
		int id = 0;
		for(conv c : convs){
			if(c.l <= x && x <= c.r) return id;
			id++;
		}
		return id;
	}
	int get_val(int x){
		for(conv c : convs) if(c.l <= x && x <= c.r){
			if(c.pa) return c.x + x;
			else return c.x;
		}
		return -1;
	}
	conv get_conv(int l, int r, int x, int y){
		int cl = get_val(x);
		int cr = get_val(y);
		if(cl == cr) return { l, r, cl, 0 };
		return { l, r, cl - l, 1 };
	}
	void simplify(){
		sort(convs.begin(), convs.end(), [](conv a, conv b){
			return a.l < b.l;
		});
		vector<conv> rconvs;
		for(conv c : convs){
			if(rconvs.empty() || !rconvs.back().can_merge(c)) rconvs.push_back(c);
			else rconvs.back() = rconvs.back() + c;
		}
	}
	node operator + (node oth){
		node ans;
		for(conv c : convs){
			if(c.pa){
				int l = c.l, r = c.r;
				while(l <= r){
					int desired = oth.get_id(c.x + l);
					int lo = l + 1, hi = r, best = l;
					while(lo <= hi){
						int mid = (lo + hi)>>1;
						if(oth.get_id(c.x + mid) == desired){
							best = mid;
							lo = mid + 1;
						} else {
							hi = mid - 1;
						}
					}
					ans.convs.push_back(oth.get_conv(l, best, c.x + l, c.x + best));
					l = best + 1;
				}	
			} else {
				ans.convs.push_back({c.l, c.r, oth.get_val(c.x), 0});
			}
		}
		ans.simplify();
		return ans;
	}
};
int main(){
	int X; cin >> X;
	int k; cin >> k;
	vector<int> pts(k + 2); for(int i = 0; i < k; i++) cin >> pts[i + 1];
       	pts.back() = 1'000'000'001;
	int q; cin >> q;
	int pt = 0;
	node cur;
	cur.convs.push_back({0, X, 0, 1});
	for(int i = 0; i < q; i++){
		int t, a; cin >> t >> a;
		while(pts[pt + 1] <= t){
			int sz = pts[pt + 1] - pts[pt];
			node now;
			if(pt&1){
				if(sz <= X)
					now.convs.push_back({0, X - sz, sz, 1});
				now.convs.push_back({max(0, X - sz + 1), X, X, 0});
			} else {
				now.convs.push_back({0, min(sz, X), 0, 0});
				if(sz < X)
			       		now.convs.push_back({sz + 1, X, -sz, 1});
			}
			cur = cur + now;	
			pt++;
		}
		int now = cur.get_val(a);
		if(pt&1){
			now += t - pts[pt];
			now = min(now, X);
		} else {
			now -= t - pts[pt];
			now = max(now, 0);
		}
		cout << now << endl;
	}	
	return 0;
}


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

int main()
{
    int n, m;
    int* A;
    int* b;

    cin >> n >> m;
    A = new int[n*m];
    b = new int[m];

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

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

    int* ret;
    ret = new int[n];

    for (int i = 0; i < n; i++)
    {
        ret[i] = 0;
        for (int j = 0; j < m; j++)
        {
            ret[i] += b[j] * A[(i * m) + j];
        }
    }

    for (int i = 0; i < n; i++)
    {
        cout << ret[i] << endl;
    }

    delete A;
    delete b;
    delete ret;

    cin >> n;
}




Measured memory_bytes: 3108
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b))<EPS)

class Point {
public:
	double x, y;
	Point(){}
	Point(double xx,double yy) {
		x = xx;
		y = yy;
	}
	Point operator + (Point& p) { return Point(x + p.x, y + p.y); }
	Point operator - (Point& p) { return Point(x - p.x, y - p.y); }
	Point operator * (double k) { return Point(x * k,y * k); }
	Point operator / (double k) { return Point(x / k,y / k); }

	double norm() { return x * x + y * y; }
	double abs() { return sqrt(norm()); }

	bool operator == (const Point& p) const {
		return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS;
	}
};
struct Segment {
	Point p1, p2;
};
typedef Point Vector;
typedef Segment Line;
class Circle {
public:
	Point c;
	double r;
	Circle(Point cc,double rr) {
		c = cc;
		r = rr;
	}
};

double dot(Vector a, Vector b) {
	return a.x * b.x + a.y * b.y;
}
double cross(Vector a, Vector b) {
	return a.x* b.y - a.y * b.x;
}
bool isOrthogonal(Vector a, Vector b) {
	return equals(dot(a, b), 0.0);
}
bool isParallel(Vector a, Vector b) {
	return equals(cross(a, b), 0.0);
}

int main() {
	int q;
	cin >> q;
	Point a, b, c, d;
	Vector v1, v2;
	for (int i = 0; i < q; i++) {
		cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y;
		v1 = a - b;
		v2 = c - d;
		if (isOrthogonal(v1, v2)) {
			cout << 1 << endl;
		}
		else if (isParallel(v1, v2)) {
			cout << 2 << endl;
		}
		else {
			cout << 0 << endl;
		}
	}
}


Measured memory_bytes: 3212
n = int(input())
s = [input() for i in range(n)]
c = [0, 0, 0, 0, 0]
cnt = 0
ans = 0

for i in s:
    if i[0] == 'M':
        c[0] += 1
    elif i[0] == 'A':
        c[1] += 1
    elif i[0] == 'R':
        c[2] += 1
    elif i[0] == 'C':
        c[3] += 1
    elif i[0] == 'H':
        c[4] += 1
    else:
        cnt += 1

for i in range(5):
    for j in range(i+1, 5):
        for k in range(j+1, 5):
            ans += c[i]*c[j]*c[k]
print(ans)

Measured memory_bytes: 9776
##########################################
inf=10**9
import heapq
class Dijkstra():
    """
    ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
    ・負のコストがない場合のみ
    ・計算量はO(E log|V|)　
    ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
    """    
    class Edge():
        #重み付き有向辺
        
        def __init__(self, _to, _cost):
            self.to =_to
            self.cost = _cost
    
    def __init__(self, V):
        #引数Vは頂点数
        self.G = [[] for _ in range(V)] #隣接リストG[u][i]が頂点uのi番目の辺
        self. _E = 0 #辺の数
        self._V = V #頂点数
    
    #proparty - 辺の数
    def E(self):
        return self._E
    
    #proparty - 頂点数
    def V(self):
        return self._V
    
    def add(self, _from, _to, _cost):
        #2頂点と辺のコストを追加
        self.G[_from].append(self.Edge(_to,_cost))
        self._E +=1
        
    def add2(self, _from, _to, _cost):
        #2頂点と辺のコスト（無向）を追加
        self.G[_from].append(self.Edge(_to, _cost))
        self.G[_to].append(self.Edge(_from, _cost))
        self._E +=1
        
    def shortest_path(self,s):
        #始点sから頂点iまでの最短経路長のリストを返す
        
        que = [] #priority queue
        d = [inf] * self.V()
        prev = [None]*self.V() #prev[j]は，sからjへ最短経路で行くときのjの一つ前の場所
        d[s] = 0
        heapq.heappush(que,(0,s)) #始点の距離と頂点番号をヒープに追加
        
        while len(que)!=0:
            #キューに格納されてある中で一番コストが小さい頂点を取り出す
            cost,v = heapq.heappop(que)
            
            #キューに格納された最短経路長候補がdの距離よりも大きい場合に処理をスキップ
            if d[v] < cost:
                continue
                
            #頂点vに隣接する各頂点iに対して，vを経由した場合の距離を計算して，これがd[i]よりも小さい場合に更新
            for i in range(len(self.G[v])):
                e = self.G[v][i] #vのi個目の隣接辺
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost #更新
                    prev[e.to] = v
                    heapq.heappush(que,(d[e.to],e.to)) #queに新たな最短経路長候補を追加

        return d
########################

#グラフの頂点を3倍化

import sys
input = sys.stdin.readline

N,M=map(int,input().split())
djk = Dijkstra(N*3)

for i in range(M):
    u,v=map(int,input().split())
    u-=1
    v-=1
    djk.add(u,N+v,1)
    djk.add(N+u,2*N+v,1)
    djk.add(2*N+u,v,1)
S,T=map(int,input().split())

d = djk.shortest_path(S-1)
ans=d[T-1]//3
if ans==inf//3:
    ans=-1
print(ans)

Measured memory_bytes: 120100
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int q = sc.nextInt();
        int[] a = new int[q];
        int[] participant = new int[n];
        for (int i = 0; i < a.length; i++) {
            a[i] = sc.nextInt();
        }
        for (int i = 0; i < participant.length; i++) {
            participant[i] = k;
        }
        for (int i = 0; i < a.length; i++) {
            participant[a[i] - 1]++;
        }
        for (int i = 0; i < participant.length; i++) {
            participant[i] -= q;
        }
        for (int i = 0; i < participant.length; i++) {
            if (participant[i] > 0) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
        sc.close();
    }
}

Measured memory_bytes: 81756
// Aizu 0243: Filling Game
// 2017.9.22 bal4u@uu

#include <stdio.h>
#include <string.h>

typedef struct { int r, c; } Q;
Q q[3000]; int top, end;
char mk[10][10];
int mv[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
char map[10][10]; int h, w;
int ans;

int check(char p[10][10])
{
	int r, c, k = p[0][0];
	for (r = 0; r < h; r++) for (c = 0; c < w; c++) if (p[r][c] != k) return 0;
	return 1;
}

void combi(int c0, int k, char p[10][10])
{
	int i, j, r, c, r2, c2;
	char t[10][10];

//	for (r = 0; r < h; r++) { for (c = 0; c < w; c++) printf("%d ", p[r][c]);printf("\n"); } printf("\n");

	if (k > ans || k > 18) return;
	for (j = 0; j <= 2; j++) {
		if (j == c0) continue;
		memcpy(t, p, sizeof(t)); t[0][0] = j;
		q[0].r = q[0].c = 0, top = 0, end = 1, memset(mk, 0, sizeof(mk)), mk[0][0] = 1;
		while (top < end) {
			r = q[top].r, c = q[top++].c;
			for (i = 0; i < 4; i++) {
				r2 = r + mv[i][0], c2 = c + mv[i][1];
				if (r2 < 0 || r2 >= h || c2 < 0 || c2 >= w || t[r2][c2] != c0 || mk[r2][c2]) continue;
				mk[r2][c2] = 1, t[r2][c2] = j, q[end].r = r2, q[end++].c = c2;
			}
		}
		if (check(t)) { if (k < ans) ans = k+1; return; }
		combi(j, k+1, t);
	}
}

int main()
{
	int r, c;
	char s[10];

	while(scanf("%d%d", &w, &h) && w) {
		for (r = 0; r < h; r++) for (c = 0; c < w; c++) {
			scanf("%s", s); map[r][c] = (*s == 'R' ? 0 : (*s == 'G' ? 1 : 2));
		}
		ans = 10000;
		if (check(map)) ans = 0;
		else combi(map[0][0], 0, map);
		printf("%d\n", ans);
	}
	return 0;
}

Measured memory_bytes: 1856
#include<bits/stdc++.h>
#define endl '\n'
#define fastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define trace1(x)                cout<<#x<<": "<<x<<endl
#define trace2(x, y)             cout<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cout<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define pb push_back
#define ff first
#define ss second
#define all(v) (v).begin(), (v).end()

using namespace std;

int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a%b);
}
int lcm(int a, int b){
    return (a*b)/gcd(a,b);
}
int ncr(int n, int k){
    int res = 1;
    if ( k > n - k )
        k = n - k;

    for (int i = 0; i < k; ++i){
        res *= (n - i);
        res /= (i + 1);
    }
    return res;
}

int fibonacci(int n){
    double phi = (1LL + sqrt(5))/(double)2;
    int nth_fib = round(pow(phi,n)/sqrt(5));
    return nth_fib;
}
bool checkYear(int year)  
{  

    if (year % 400 == 0)  
        return true;  
  
    if (year % 100 == 0)  
        return false;  

    if (year % 4 == 0)  
        return true;
        
    return false;  
}
signed main(){

    fastIO

    int n;
    cin >> n;
    int ar[n], br[n];
    for(int i =0; i<n; i++) cin >> ar[i];
    for(int i =0; i<n; i++) cin >> br[i];
    priority_queue<int> pq;
    for(int i =0; i<n ; i++){
        if(ar[i] - br[i] > 0){
            pq.push(ar[i] - br[i]);
        }    
    }
    int ans = 0;
    while(!pq.empty()){
        ans += pq.top();
        pq.pop();
    }
    cout << ans ;
    
    return 0;
}


Measured memory_bytes: 256
import math
import sys
input = sys.stdin.readline

k = int(input())

n = 512
pattern = 0
a = []
for i in range(n):
    val = math.factorial(7 + i) // math.factorial(i) // math.factorial(7)
    a.append(val)
a.reverse()

cnt = 600 * 7 
ans = ["FESTIVA" for _ in range(n)]
for i, item in enumerate(a):
    ans[i] += ("L" * (k // item))
    k %= item
ans.reverse()
print("".join([str(item) for item in ans]))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define ll long long int
const ll mod=1e9+7;
const int maxn=2e5+50;
using namespace std;
int main()
//int found; found=chaine.find(cara); if (found!=std::string::npos) how to verify if a caracter exists in a chaine
// toupper(caractere) ==> return the majuscule of a caractere
//floor(x) Returns the largest integer smaller than x
//ceil(x) returns  Returns the smallest integer greater
{
	int n;
	cin>>n;
	bool b;
	b=false;
	for(int d=1;d<=9;d++)
	{
		if(n%d==0)
		{
			if(n/d<10)
			{
				b=true;
			}
		}
	}
	if(b)
	{
		cout<<"Yes";
	}
	else
	{
		cout<<"No";
	}
}



Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define w(t) int t; cin>>t;while(t--)
#define ps(x, y) fixed<<setprecision(y)<<x
// double ans = 1.012345668992
//cout<<ps(ans , 6)
// ans = 1.012345 // 6 decimal places
#include<iomanip>
#include<cmath>
#include "cmath"
#include "iostream"
void pi() {

	// Find value of pi using
	// asin() function
	double pi = 2 * asin(1.0);

	// Print value of pi
	printf("%f\n", pi);
}

const double PI = 3.14159264;
int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt" , "r", stdin);
	//freopen("output.txt" , "w", stdout);
#endif
	int k;
	cin >> k;
	string s;
	cin >> s;
	if (s.size() <= k)cout << s << "\n";
	else {
		string st = s.substr(0, k);
		st += "...";
		cout << st << "\n";
	}

	return 0;


}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=(a); i<=(b); i++)
#define per(i,a,b) for (int i=(a); i>=(b); i--)
using namespace std;

const int maxn = 100005;
int del[maxn], c[maxn], n, x, y, rt, ans;
vector<int> e[maxn];

int dfs(int u, int fa) {
	int son = 0, sum = 0, sz = e[u].size();
	rep (i, 0, sz - 1)
		if (e[u][i] != fa && !del[e[u][i]]) {
			sum += dfs(e[u][i], u);
			son++;
		}
	// printf("%d %d\n", u, fa);
	if (sum < son - 1) ans += son - 1 - sum;
	return son >= 1;
}

int main() {
	scanf("%d", &n);
	rep (i, 2, n) {
		scanf("%d%d", &x, &y);
		c[++x]++; c[++y]++;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	rep (i, 1, n)
		if (c[i] == 2) {
			int a = 0, b = 0, sz = e[i].size();
			rep (j, 0, sz - 1)
				if (!del[e[i][j]]) {
					if (!a) a = e[i][j];
					else b = e[i][j];
				}
			e[a].push_back(b);
			e[b].push_back(a);
			del[i] = 1;
		}
		else if (c[i] > 2) rt = i;
	if (!rt) puts("1");
	else { dfs(rt, 0); cout << ans << endl; }
	return 0;
}

Measured memory_bytes: 8064
#include<iostream>
#include<vector>
#include<complex>
#include<utility>
#include<queue>
#include<cmath>
#include<iomanip>

typedef long double ld;
typedef std::complex<ld> P;
const ld eps = 1e-8, pi = acos(-1.0);
struct L { P a, b; };

namespace std {
  bool operator<(const P &lhs, const P &rhs) {
    return lhs.real() == rhs.real() ? lhs.imag() < rhs.imag()
      : lhs.real() < rhs.real();
  }
}

using namespace std;

ld dot(P a, P b) { return real(conj(a) * b); }
ld cross(P a, P b) { return imag(conj(a) * b); }
int ccw(P a, P b, P c) {
  b -= a, c -= a;
  if (cross(b, c) > eps) return 1;
  if (cross(b, c) < -eps) return -1;
  if (dot(b, c) < 0) return 2;
  if (norm(b) < norm(c)) return -2;
  return 0;
}

bool isis_sp(L s, P p) {
  return abs(s.a - p) + abs(s.b - p) - abs(s.b - s.a) < eps;
}


P is_ll(L s, L t){
  P sv = s.b - s.a, tv = t.b - t.a;
  return s.a + sv * cross(tv, t.a - s.a) / cross(tv, sv);
}

bool isis_ss(L s, L t) {
  return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 &&
    ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}

P proj(L l, P p) {
  ld t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
  return l.a + t * (l.a - l.b);
}

ld dist_pp(P p, P q) {
  return abs(p - q);
}

ld dist_sp(L s, P p) {
  P r = proj(s, p);
  if (isis_sp(s, r)) return abs(r - p);
  return min(abs(s.a - p), abs(s.b - p));
}

ld dist_ss (L s, L t) {
  if (isis_ss(s, t)) return 0;
  ld a = min(dist_sp(s, t.a), dist_sp(t, s.a));
  ld b = min(dist_sp(s, t.b), dist_sp(t, s.b));
  return min(a, b);
}

P rotate(ld deg, P p) {
  ld rad = deg * pi / 180.0;
  return polar((ld)1.0, rad) * p;
}

struct Star { L e[5]; };

ld dist_stst(Star s, Star t) {
  ld val = dist_ss(s.e[0], t.e[0]);
  for (L ss : s.e) for (L ts : t.e) {
    val = min(val, dist_ss(ss, ts));
  }
  return val;
}

int main() {
  int n, m, l;
  while (cin >> n >> m >> l and n) {
    m--; l--;
    vector<Star> stars(n);
    for (Star &s : stars) {
      int x, y ,a, r;
      cin >> x >> y >> a >> r;
      P center(x, y);
      for (int i = 0; i < 5; i++) {
        s.e[i].a = 
          center + polar((ld)r, (90 + a + 72 * i) * pi / 180.0);
        s.e[i].b = 
          center + polar((ld)r, (90 + a + 72 * (i + 2)) * pi / 180.0);
      }
    }

    vector<vector<ld>> dist(n);
    for (vector<ld> &v : dist) {
      v.reserve(n);
    }

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        dist[i][j] = dist_stst(stars[i], stars[j]);
      }
    }

    for (int k = 0; k < n; k++) {
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
      }
    }

    cout << fixed << setprecision(30)<< dist[m][l] << endl;
  }
}

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

int main() {
	static long long N, A[100000], ANS = 1, MOD = 1000000007;
	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i], A[i]++;
	long long X[100010] = {};
	X[0] = 3;
	for (int i = 0; i < N; i++) {
		ANS *= X[A[i] - 1];
		ANS %= MOD;
		X[A[i] - 1]--;
		X[A[i]]++;
	}
	cout << ANS << endl;
}

Measured memory_bytes: 1792
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>
#include <numeric>

using namespace std;

#define mod 1000000007

int main()
{
	int n;
	cin >> n;
	cout << "ABC" << n << endl;
}

Measured memory_bytes: 256
N = int(input())
P = list(map(int,input().split()))
A = []
for i in range(N-1):
    if P[i]>P[i+1]:
        A.append([(P[i],i),(P[i+1],i+1)])
l = len(A)
if l > 2 or l == 1:
    print("NO")
elif l == 0:
    print("YES")
elif l == 2:
    a = max(A[0])
    b = min(A[1])
    P[a[1]],P[b[1]] = b[0],a[0]
    for j in range(N-1):
        if P[j] > P[j+1]:
            print("NO")
            j = "j"
            break
    if j != "j":
        print("YES")


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

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> VI;
typedef vector<VI> VVI;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = numeric_limits<int>::max() / 2;
const int NEG_INF = numeric_limits<int>::min() / 2;
const int MOD = 1e9 + 7;

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

    int n, m, l, k, a, h;
    //????????°?????´???????????§?????¶??????????????????????¨??????°??????????????°???????????????????????¢??????
    while (true)
    {
        cin >> n >> m >> l >> k >> a >> h;
        if (n == 0)
            break;
        VVI dis(n, vector<int>(n, INF));
        for (int i = 0; i < n; i++)
            dis[i][i] = 0;
        bool f[n + 1] = {false};
        f[a] = true;
        f[h] = true;
        for (int i = 0; i < l; i++)
        {
            int c;
            cin >> c;
            f[c] = true;
        }
        for (int i = 0; i < k; i++)
        {
            int x, y, t;
            cin >> x >> y >> t;
            dis[x][y] = t;
            dis[y][x] = t;
        }
        for (int k = 0; k < n; k++)
        {
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
                }
            }
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (!f[i] || !f[j] || dis[i][j] > m)
                    dis[i][j] = INF;
            }
        }
        for (int k = 0; k < n; k++)
        {
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
                }
            }
        }
        if (dis[a][h] == INF)
        {
            cout << "Help!" << endl;
        }
        else if (dis[a][h] <= m)
        {
            cout << dis[a][h] << endl;
        }
        else
        {
            cout << dis[a][h] * 2 - m << endl;
        }
    }
}


Measured memory_bytes: 3116
import collections
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    a = list(map(int,input().split()))
    max_a = max(a)
    count = [0 for _ in range(max_a+1)]
    c = collections.Counter(a)
    c = list(c.items())

    if len(c) == 1:
        print(c[0][1])

    elif len(c) == 2:
        if abs(c[0][0]-c[1][0]) <= 2:
            print(c[0][1]+c[1][1])
        else:
            print(max(c[0][1],c[1][1]))

    else:
        for i in range(len(c)):
            count[c[i][0]] = c[i][1]

        sum_list = [0 for _ in range(len(count)-2)]
        for i in range(len(count)-2):
            sum_list[i] = count[i]+count[i+1]+count[i+2]
        print(max(sum_list))

if __name__ == "__main__":
    main()

Measured memory_bytes: 16928
#include <iostream>
typedef long long ll;
using namespace std;

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

  ll a, b, c, k; cin >> a >> b >> c >> k;
  ll ans;
  if(k%2 == 0) ans = a-b;
  else ans = b-a;

  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 256
N = int(input())
s = input()
res = 0
for j in range(1,N-1):
    char = s[j]
    left_list = ['B', 'R']
    right_list = ['R', 'B']
    if char == 'B':
        left_list = ['G', 'R']
        right_list = ['R', 'G']
    elif char == 'R':
        left_list = ['B', 'G']
        right_list = ['G', 'B']
    for left, right in zip(left_list, right_list):
        left_idx = [j-i for i, x in enumerate(s[:j]) if x==left]
        right_idx = [i+1 for i, x in enumerate(s[j+1:]) if x==right]
        left_len = len(left_idx)
        right_len = len(right_idx)
        tmp = left_len * right_len
        tmp += len(set(left_idx) | set(right_idx)) - left_len - right_len
        res += tmp
print(res)

Measured memory_bytes: 84796
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

#define sf scanf
#define pb push_back

const int N = 1e5+7;
int dist1[N], dist2[N];
vector <int> v[N];

void dfs1(int x, int depth) {
	if (dist1[x] != -1) return;
	dist1[x] = depth;
	for(auto i : v[x]) {
		dfs1(i, depth+1);
	}
}

void dfs2(int x, int depth) {
	if (dist2[x] != -1) return;
	dist2[x] = depth;
	for(auto i : v[x] ) {
		dfs2(i, depth+1);
	}
}

int main() {
	int n; sf("%d", &n);
	for(int i=0; i<n-1; i++) {
		int a, b;
		sf("%d %d", &a, &b);
		v[a].pb(b); v[b].pb(a);
	}
	for(int i=0; i<N; i++) {dist1[i] = -1; dist2[i] = -1;}
	dfs1(1, 0); dfs2(n, 0);
	int cnt1 = 0, cnt2 = 0;
	for(int i=1; i<=n; i++) {
		if (dist1[i] <= dist2[i]) cnt1++;
		else cnt2++;
	}
	if (cnt1 > cnt2) printf("Fennec\n");
	else printf("Snuke\n");
}

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

using namespace std;

int n;

void go(string s, int mask) {
  if (s.size() == n) {
    cout << s << '\n';
    return;
  }
  for (int i = 0; i < 26; ++i) {
    string c;
    c += char(i + 'a');
    go(s + c, mask | (1 << i));
    if (!((mask >> i) & 1)) {
      return;
    }
  }
}

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

  cin >> n;
  go("a", 1);

  return 0;
}


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

int main(){
	int N, M, temp = 0, sum = 0;
	cin >> N >> M;
	int C[M], L[M - 1];//coordinate
	for(int i = 0; i < M; i++){
		cin >> C[i];
	}
	if(N >= M){
		cout << 0 << endl;
	}else{
		sort(C, C + M);
		for(int i = 0; i < M - 1; i++){
			L[i] = C[i + 1] - C[i];
		}
		sort(L, L + (M - 1), greater<int>());
		for(int i = 0; i < N - 1; i++){
			sum += L[i];
		}
		cout << C[M-1] - C[0] - sum << endl;
	}
	return 0;
}


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

int main() {
    int N, sw = 0;
    cin >> N;

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

    for (int i = 0; i < N; i++) {
        int minj = i;

        for (int j = i; j < N; j++) {
            if (A[j] < A[minj]) {
                minj = j;
            }
        }

        if (minj != i) {
            swap(A[i], A[minj]);
            sw++;
        }
    }

    for (int i = 0; i < N; i++) {
        if (i > 0) {
            cout << " ";
        }
        cout << A[i];
    }
    cout << endl;

    cout << sw << endl;

    return 0;
}

Measured memory_bytes: 3092
package main

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

func main() {
	N := ReadInt()
	a := ReadInts(N)
	s := make([]int, 1e5+5)
	for _, ai := range a {
		l := ai - 1
		r := l + 3
		if l < 0 {
			l = 0
		}
		s[l]++
		s[r]--
	}
	sum := 0
	max := -1
	for i, vi := range s {
		sum += vi
		s[i] = sum
		if max < sum {
			max = sum
		}
	}
	fmt.Println(max)
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


Measured memory_bytes: 4036
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>

using namespace std;

#define ll long long
#define ld long double

#define rep(i, n)      for (int i = 0; i < (int)(n); ++i)
#define rep3(i, m, n)  for (int i = (m); i < (int)(n); ++i)
#define rrep(i, n)     for (int i = (int)(n)-1; i >= 0; --i)
#define rrep3(i, m, n) for (int i = (int)(n)-1; i >= (m); --i)
#define all(x) begin(x), end(x)
#define rall(x) end(x), begin(x)

#define endl '\n'


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

ll solve(string S, string T) {
  int res = 0;
  rep(i,S.length()) if (S[i] == T[i]) res++;
  return res;
}

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

  string S, T;
  cin >> S >> T;

  auto ans = solve(S, T);
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3196
//long long -> ll
//http://web.mit.edu/~ecprice/acm/acm08/notebook.html#file12
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include<bits/stdc++.h>
typedef long long ll;
#define x first
#define y second
#define all(aaa) (aaa).begin(),(aaa).end()
#define REP(i,sss,eee) for(long long i=sss;i<=eee;++i)
#define pb push_back
#define pii pair<long long,long long>
#define vi vector<long long>
#define speed ios_base::sync_with_stdio(0);cin.tie(0);
#define N 1000000007
using namespace __gnu_pbds;
using namespace std;
template <class T>
T MAX(T a, T b){return ((a>b)?a:b);}
template <class T>
T MIN(T a, T b){return ((a<b)?a:b);}
template <class T>
T MOD(T a){return ((a>=0)?a:(-1*a));}
template <class T>
void SWAP(T &a,T &b){T temp=a;a=b;b=temp;}

typedef tree<
long long,
null_type,
less<long long>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

long long ex(long long a, long long b){
	if(b==0||a==1){return 1;}
	if(a==0||b==1){return a;}
	long long tmp=ex(a,(b/2));
	if(b%2){return ((((tmp*tmp)%N)*a)%N);}
	else{return ((tmp*tmp)%N);}
}
long long inv(long long k){
	if(k==1){return 1;}
	else{return ex(k,N-2);}
}
/*****************default********************/
long long solve()
{
	string k;long long d;cin>>k>>d;
	reverse(k.begin(),k.end());
	long long n=k.size();
	std::vector<std::vector<long long>> f(10003,std::vector<long long>(d,0));
	std::vector<long long> g(10003,0);
	long long tot=0;REP(i,0,n-1){(tot+=(k[i]-'0'));}
	if(tot%d==0){g[0]=1;}
	tot=((((tot-(k[0]-'0'))%d)+d)%d);
	long long highest=(k[0]-'0');
	for(long long i=0;i<highest;++i)
	{
		(f[0][i%d])++;
	}
	g[1]=g[1]+f[0][(d-tot)%d];
	for(long long i=highest;i<=9;++i)
	{
		(f[0][i%d])++;
	}
	for(long long i=1;i<n;++i)
	{
		tot=((((tot-(k[i]-'0'))%d)+d)%d);
		highest=(k[i]-'0');
		g[i]=(g[i]+g[i-1])%N;
		for(long long val=0;(val<highest);++val)
		{
			for(long long rem=0;rem<d;++rem){f[i][(val+rem)%d]=(f[i][(val+rem)%d]+f[i-1][rem])%N;}
		}
		g[i+1]=((g[i+1]+f[i][(d-tot)%d])%N);
		for(long long val=highest;(val<10);++val)
		{
			for(long long rem=0;rem<d;++rem){f[i][(val+rem)%d]=(f[i][(val+rem)%d]+f[i-1][rem])%N;}
		}
	}
	//cout<<g[n]<<" "<<g[n-1]<<"\n";
	cout<<((g[n]+g[n-1]-1)%N)<<"\n";
}
signed main(){
	speed
	long long tt=1;
	//cin>>tt;
	while(tt--)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 8576
#include <stdio.h>
#include <iostream>
#include <string>
 
using namespace std;
 
char changeit(char c){
    char n = c;
    if(65 <= n && n <= 90){
        n = n + 32;
    }
    else if(97 <= n && n <= 122){
        n = n - 32;
    }
    return n;
}
 
int main(){
    string s;
    getline(cin, s);
    int n = s.length();
    for(int i = 0; i < n; i++){
        cout << changeit(s[i]);
    }
    cout << "\n";
}


Measured memory_bytes: 3172
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<tuple>
#include<ctime>
#include<functional>
#include<cmath>
#include<cassert>
using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))

int main(){
    int X;
    cin>>X;
    int ans;
    ans=(X/500)*1000+((X%500)/5)*5;
    p(ans);

}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

const double eps = 1e-15;

class Point
{
public:
    double x, y;
    Point() : x(0), y(0) {}
    Point(double _x, double _y) : x(_x), y(_y) {}
};

istream& operator >> (istream& in, Point& P)
{
    in >> P.x >> P.y;
    return in;
}

ostream& operator << (ostream& out, const Point& P)
{
    out << P.x << " " << P.y;
    return out;
}

ostream& operator << (ostream& out, vector<Point> vP)
{
    size_t n = vP.size();
    for (int i = 0; i < n; ++i) {
        out << vP[i] << endl;
    }
    return out;
}

double Dist(const Point& P, const Point& Q)
{
    double dx = P.x - Q.x;
    double dy = P.y - Q.y;
    return sqrt(dx * dx + dy * dy);
}

double FindDiameter(const vector<Point>& vP)
{
    int i = 0, j = 1;
    double Res = Dist(vP[i], vP[j]);

    while (1) {
        bool bUpdate = false;
        while (1) {
            if (j < vP.size() - 1 && Dist(vP[i], vP[j]) < Dist(vP[i], vP[j+1])) {
                Res = max(Res, Dist(vP[i], vP[j+1]));
                j++;
                bUpdate = true;
            } else {
                break;
            }
        }
        while (1) {
            if (Dist(vP[i], vP[j]) < Dist(vP[i+1], vP[j])) {
                Res = max(Res, Dist(vP[i+1], vP[j]));
                i++;
                bUpdate = true;
            } else {
                break;
            }
        }
        if (j == vP.size() - 1) break;
        if (!bUpdate) ++i;
    }


    return Res;
}

int main()
{
    int n;
    cin >> n;
    vector<Point> vP(n);
    for (int i = 0; i < n; ++i) {
        cin >> vP[i];
    }

    cout << fixed << setprecision(10);
    cout << FindDiameter(vP);

    return 0;
}


Measured memory_bytes: 4064
import std.stdio;
import std.algorithm;
import std.conv;
import std.string;
import std.array;
import std.math;

void main(string[] args) {
  auto input = readln().chomp.split.map!(to!int).array;

  if(input[1] == 100){input[1]++;}

  auto ans = input[1] * pow(100,input[0]);
  ans.writeln;
}

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

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

using namespace std;

const int MOD=1000000007;

int three[1000001];

string s;

int dfs(int i,bool b){
	if(i==s.length()) return 1;

	if(b){
		if(s[i]=='1'){
			return (2LL*dfs(i+1,true)%MOD+dfs(i+1,false))%MOD;
		}
		else{
			return dfs(i+1,true);
		}
	}
	else{
		return three[s.length()-i];
	}
}

int main(){
	three[0]=1;
	rep(i,1000000) three[i+1]=three[i]*3LL%MOD;

	cin>>s;
	cout<<dfs(0,true)<<endl;

	return 0;
}


Measured memory_bytes: 7552
#include <stdio.h>

int isSame(const int *A,const int *B)
{
	int p1, p2, t1, t2, f1, f2, e, h;

	h = 0;
	for (p1 = 0; p1 < 6; p1++)
	{
		if (A[0] == B[p1] && A[5] == B[5 - p1])
		{
			h = 1;
			break;
		}
	}
	if (!h) return 0;

	h = 0;
	for (p2 = 0; p2 < 6; p2++)
	{
		if (p2 == p1 || p2 == 5 - p1) continue;
		if (A[1] == B[p2] && A[4] == B[5 - p2])
		{
			h = 1;
			break;
		}
	}
	if (!h) return 0;

	t1 = p1 / 3;
	t2 = t1 > 0 ? 3 - (t1 + p1 % 3) : p1 % 3;
	f1 = p2 / 3;
	f2 = f1 > 0 ? 3 - (f1 + p2 % 3) : p2 % 3;

	e = t1 ^ f1;
	e = f2 - (t2 + 1) % 3 != 0 ? !e * 3 : e * 3;
	e += e > 0 ? (t2 + f2) - 1 : 3 - (t2 + f2);
		
	if (A[2] != B[e] || A[3] != B[5 - e]) return 0;

	return 1;	
}

int main()
{
	int A[6];
	int B[6];
	int i;

	for (i = 0; i < 6; i++) scanf("%d", &A[i]);
	for (i = 0; i < 6; i++) scanf("%d", &B[i]);

	if (isSame(A, B)) printf("Yes\n");
	else printf("No\n");

	return 0;

}



Measured memory_bytes: 2148
#include<stdio.h>

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

	int A[n];
	for(int i=0; i<n; ++i){
		scanf("%d", &A[i]);
	}
	int x = A[n-1];

	// Partition
	int i = -1;
	int temp;
	for(int j=0; j<n-1; ++j){
		if(x < A[j]){
			continue;
		}else{
			i += 1;
			temp = A[i];
			A[i] = A[j];
			A[j] = temp;
		}
	}
	temp = A[i+1];
	A[i+1] = A[n-1];
	A[n-1] = temp;
	int s = i+1;

	for(int i=0; i<n; ++i){
		if(i>0)
			printf(" ");

		if(i == s){
			printf("[%d]", A[i]);
		}else{
			printf("%d", A[i]);
		}
	}	
	printf("\n");

	return 0;
}


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

const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e15)
#define PI (acos(-1))
#define EPS (1e-7)

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

int main(){
    int n, w;
    cin >> n >> w;
    vi wi(n), v(n);
    rep(i, n) cin >> wi[i] >> v[i];
    vector<vll> dp(n+1, vll(1e5+1, INF));
    dp[0][0] = 0;
    rep(i, n) rep(j, 1e5+1) {
        if (j-v[i]>=0) dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]]+wi[i]);
        else dp[i+1][j] = dp[i][j];
    }
    int ans = 0;
    rep(i, 1e5+1) if (dp[n][i] <= w) ans = max(ans, i);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 83200
N,W = map(int,input().split())
wv = [[int(x) for x in input().split()] for i in range(N)]
dp = [[0 for j in range(W+1)] for i in range(N+1)]
for i in range(N):
    for sum_w in range(W+1):
        if wv[i][0] + sum_w < W+1 and dp[i+1][wv[i][0]+sum_w] < dp[i][sum_w] + wv[i][1]:
            dp[i+1][wv[i][0]+sum_w] = dp[i][sum_w] + wv[i][1] #dp[i][weight_i + sum_weight]
        if dp[i+1][sum_w] < dp[i][sum_w]:
            dp[i+1][sum_w] = dp[i][sum_w]
print(dp[N][W])

Measured memory_bytes: 171784
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<utility>
#include<cstdio>
#include<set>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include <bitset>
using namespace std;
const int mod=1e9+7;
#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,x,n) for (int i= x;i<n;i++)
#define all(v) v.begin(), v.end()
#define nepe(v) next_permutation(all(v))
#define F first 
#define S second
#define PB push_back 
#define MP make_pair
using ll = long long;
using vi = vector<int>; 
using vvi = vector<vi>;
using vl=vector<long long>;
using vvl = vector<vl>;
using vp =vector<pair<int,int>>;

typedef pair<int,int> P;
string s;
int k;
ll INF = 1000000000000;

int main(){
    int H,W,A,B;
    cin >>H>>W>>A>>B;
    rep(i,B){
        rep(j,A) cout <<1;
        rep(j,W-A) cout <<0;
        cout <<endl;
    }
    rep(i,H-B){
        rep(j,A) cout <<0;
        rep(j,W-A) cout <<1;
        cout <<endl;
    }
}


Measured memory_bytes: 1280
def main():
    n = int(input())
    h_list = list(map(int, input().split()))

    for i in range(n-1):
        if h_list[i] < h_list[i+1]:
            h_list[i+1] -= 1

        elif h_list[i] > h_list[i+1]:
            print("No")
            exit()

    print("Yes")


if __name__ == '__main__':
    main()


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

n=int(input())
A=list(map(int, input().split()))
#a=1
init=1
#maxa=99999999999999999999999999
#maxa=A[1]
B1=[]
for i in A:
    if init==1:
        a=i
        init=0
        B1.append(a)
    else:
        a=gcd(a,i)
        B1.append(a)

init=1
B2=[]
for i in A[::-1]:
    if init==1:
        a=i
        init=0
        B2.append(a)
    else:
        a=gcd(a,i)
        B2.append(a)

#print(B1)
#print(B2)
result=0
for i in range(n):
    if i==0:
        if result<B2[n-2]:
            result=B2[n-2]
    elif i==n-1:
        if result<B1[n-2]:
            result=B1[n-2]
    else:
        if result<gcd(B1[i-1],B2[n-i-2]):
            result=gcd(B1[i-1],B2[n-i-2])

print(result)

Measured memory_bytes: 14076
module.exports=function(t){var r={};function e(n){if(r[n])return r[n].exports;var o=r[n]={i:n,l:!1,exports:{}};return t[n].call(o.exports,o,o.exports,e),o.l=!0,o.exports}return e.m=t,e.c=r,e.d=function(t,r,n){e.o(t,r)||Object.defineProperty(t,r,{enumerable:!0,get:n})},e.r=function(t){"undefined"!=typeof Symbol&&Symbol.toStringTag&&Object.defineProperty(t,Symbol.toStringTag,{value:"Module"}),Object.defineProperty(t,"__esModule",{value:!0})},e.t=function(t,r){if(1&r&&(t=e(t)),8&r)return t;if(4&r&&"object"==typeof t&&t&&t.__esModule)return t;var n=Object.create(null);if(e.r(n),Object.defineProperty(n,"default",{enumerable:!0,value:t}),2&r&&"string"!=typeof t)for(var o in t)e.d(n,o,function(r){return t[r]}.bind(null,o));return n},e.n=function(t){var r=t&&t.__esModule?function(){return t.default}:function(){return t};return e.d(r,"a",r),r},e.o=function(t,r){return Object.prototype.hasOwnProperty.call(t,r)},e.p="",e(e.s=0)}([function(t,r,e){e(1)(e(2).readFileSync("/dev/stdin","UTF-8"))},function(t,r){function e(t,r){return function(t){if(Array.isArray(t))return t}(t)||function(t,r){var e=[],n=!0,o=!1,u=void 0;try{for(var i,a=t[Symbol.iterator]();!(n=(i=a.next()).done)&&(e.push(i.value),!r||e.length!==r);n=!0);}catch(t){o=!0,u=t}finally{try{n||null==a.return||a.return()}finally{if(o)throw u}}return e}(t,r)||function(){throw new TypeError("Invalid attempt to destructure non-iterable instance")}()}t.exports=function(t){for(var r=t.split("\n"),n=e(r[0].split(" ").map(function(t){return Number(t)}),2),o=n[0],u=n[1],i=r[1].split(" ").map(function(t){return Number(t)}),a=999999999,f=0;f<o-u+1;f++){var l=f+u-1,c=i[f],p=i[l],s=Math.abs(p-c),d=Math.abs(c)+s,y=Math.abs(p)+s,b=Math.min(y,d);a=Math.min(a,b)}console.log(a)}},function(t,r){t.exports=require("fs")}]);

Measured memory_bytes: 17612
import           Control.Monad
import qualified Data.ByteString.Char8       as BS
import           Data.Maybe
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as VM

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
  [h, n] <- getIntList
  abs <- V.replicateM n $ do
    [a, b] <- getIntList
    return (a, b)

  let inf = 10^9 :: Int

  -- dp[decreased hp] == minimum mp to achieve it
  dp <- VM.new (h+1)
  VM.set dp inf
  VM.write dp 0 (0::Int)

  forM_ [0..(h-1)] $ \i -> do
    mp0 <- VM.read dp i
    when (mp0 < inf) $ do
      forM_ [0..(n-1)] $ \j -> do
        let (a,b) = abs V.! j
            hp1 = min h (i+a)
            mp1 = mp0 + b
        mp1' <- VM.read dp hp1
        VM.write dp hp1 (min mp1 mp1')

  ans <- VM.read dp h
  print ans



Measured memory_bytes: 1148
n, k = map(int, input().split())
from fractions import gcd
from functools import reduce
def gcd_list(xs):
    return reduce(gcd, xs)
ns = list(map(int, input().split()))
a = gcd_list(ns)
max_n = max(ns)
if k > max_n:
    print('IMPOSSIBLE')
elif k % a == 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')


Measured memory_bytes: 88172
import heapq
n,k=map(int,input().split())
z=[0,1]
for i in range(1,n):
    z.append(z[i]+2)
s=sorted([list(map(int,input().split()))for _ in range(n)],key=lambda x:-x[1])
q=[]
v=0
ans=0
l=[0]*-~n
for a in s[:k]:
    if not l[a[0]]:
        v+=1
        ans+=z[v]
    else:
        heapq.heappush(q,a[1])
    l[a[0]]=1
    ans+=a[1]
tem=ans
for a in s[k:]:
    if not q:break
    if l[a[0]]:continue
    l[a[0]]=1
    v+=1
    t=heapq.heappop(q)
    tem=tem-t+a[1]+z[v]
    ans=max(ans,tem)
print(ans)

Measured memory_bytes: 72884
n = int(input())
a = list(map(int, input().split()))
print(' '.join([str(x) for x in a]))
for i in range(1, n) : 
	v = a[i]
	j = i - 1
	while j >= 0 and a[j] > v :
		a[j + 1] = a[j]
		j -= 1
	a[j + 1] = v
	print(' '.join([str(x) for x in a]))


Measured memory_bytes: 5608
#include <math.h>
#include <regex>
#include "bits/stdc++.h"
#define FOR(i, s, e) for (int i = int(s); i < int(e); ++i)
#define REP(i, e) FOR(i, 0, e)
#define INF (INT_MAX / 2)
#define LINF (LLONG_MAX / 2)
#define EPS (1.0e-8)
const int MGN = 10;
const int ARY_SZ_MAX = (int)1e7;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>;
using vb = vector<bool>; using vvb = vector<vb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>; using psl = pair<string, ll>;


ll MOD = 998244353;

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

  int N; cin >> N;
  vl D(N); REP(i,N) cin >> D[i];

  if (D[0] != 0) { // 1-1 の距離が 0 でない
    cout << 0 << endl;
    return 0;
  }
  FOR(i,1,N) {
    if (D[i] == 0) {
      cout << 0 << endl;
      return 0;
    }
  }

  vl h(N, 0); // h[i] : 距離が i の頂点数
  REP(i, N) h[D[i]]++;
  
  ll ans = 1LL;
  for(int i = 2; i<N; i++) {
    for(int j = 0; j < h[i]; j++) {
      ans *= h[i-1];
      ans %= MOD;
    }
  }

  cout << ans << endl;


  return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
const ll INF=100000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};


int main() {

	ll n;
	ll t,a;
	ll h[1001];
	ll c=0;
	ll min=1000000;
	ll o=0;

	cin>>n;
	cin>>t>>a;
	a=a*1000;
	for(ll i=1; i<n+1; ++i){
		cin>>h[i];
		c=t*1000-h[i]*6;
		if(fabs(c-a)<min){
			min=fabs(c-a);
			o=i;
		}
	}

	cout<<o<<endl;


	return 0;
}


Measured memory_bytes: 256