akhauriyash/Code-Regression huggingface dataset:
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.nextLine());
		List<Integer> aList = new ArrayList<Integer>();
		for (String s : sc.nextLine().split(" ")) {
			aList.add(Integer.valueOf(s));
		}
		Collections.sort(aList, Collections.reverseOrder());

		int ans = 0;
		for (int i = 0; i < n; i++) {
			if (i % 2 == 0) {
				ans += aList.get(i);
			} else {
				ans -= aList.get(i);
			}
		}

		System.out.println(ans);

		sc.close();
	}
}

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

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; 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 VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;
const ll mod = 1e9+7;


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

    ll n,m;cin>>n>>m;
    vll a(n); REP(i,n) cin>>a[i];

    vector<pair<ll,ll>> vec;
    REP(i,m){
        ll b,c; cin>>b>>c;
        vec.push_back(make_pair(c,b));
    }
    VSORTR(vec);
    ll idx=0;
    for(auto p: vec){
        ll push = min(n-idx, p.second);
        REP(i,push) a.push_back(p.first);
        idx += push;
        if (idx>=n) break;
    }
    VSORTR(a);
    cout << accumulate(a.begin(), a.begin()+n, 0LL)<<endl;
    return 0;
}

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

#define PI 3.14159265359
#define rep(i,a,n) for(int i=a;i<(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define descSort(a) sort(a.begin(),a.end(),std::greater<int>())
using namespace std;
typedef long long ll;
const ll INF = 1e9 + 7;

int main(void)
{
    ll n;
    cin>>n;
    vector<ll> a(n);
    rep(i,0,n)cin>>a[i];

    ll ans=0;
    rep(i,1,n){
        ll diff=a[i-1]-a[i];
        if(diff>0){
            ans+=diff;
            a[i]+=diff;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 4828
#include<stdio.h>
int main(void){
	int d,w,h,n,i,r,max,l;
	while(1){
		scanf("%d%d%d",&d,&w,&h);
		if(d==0&&w==0&&h==0)break;
		max=d; l=w*w+h*h;
		if(max<w){max=w; l=d*d+h*h;}
		if(max<h){max=h; l=w*w+d*d;}
		scanf("%d",&n);
		for(i=0;i<n;i++){
			scanf("%d",&r);
			printf(l<r*r*4?"OK\n":"NA\n");
		}
	}
	return 0; 
}

Measured memory_bytes: 584
#include <stdio.h>
#include <math.h>

int main(){
	double x1,x2,x3,y1,y2,y3,xp,yp,A,B,C;
	double s,t;

	while(scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3,&xp,&yp)!=EOF){
		A=(x2-x1)*(y3-y1) - (x3-x1)*(y2-y1);
		B=(xp-x1)*(y3-y1) - (x3-x1)*(yp-y1);
		C=(x2-x1)*(yp-y1) - (xp-x1)*(y2-y1);

		s=B/A;
		t=C/A;

		if(s>0 && t>0 && 0<s+t && s+t<1){printf("YES\n");}
		else{printf("NO\n");}

	}
	return 0;
}

Measured memory_bytes: 612
#%%
H, W = map(int, input().split())
N = int(input())
a = list(map(int, input().split()))

import numpy as np
l = []

for i in range(len(a)):
    for j in range(a[i]):
        l.append(i+1)

l = np.array(l)
l = l.reshape(H, W)

for i in range(0, H):
    if i % 2 == 0:
        print(' '.join(map(str, l[i].tolist())))
    else:
        print(' '.join(map(str, l[i][::-1].tolist())))



#%%


Measured memory_bytes: 12760
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    string s;
    cin >> s;
    int flag=1;
    for(char c='a';c<='z';c++){
        int cnt=0;
        for(int i=0;i<s.size();i++){
            if(s[i]==c) cnt++;
        }
        if(cnt%2==1){
            flag=0;
            break;
        }
    }

    if(flag) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include <iostream>

#define NMAX 200005

using namespace std;

unsigned long long N, K;
int A[NMAX];
int cycle_end = 0;
int cycle_start = 0;
int cycle_length = 0;
int position[NMAX];
int where_is[NMAX];
bool visited[NMAX];

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

    position[0] = 1;
    where_is[1] = 0;
    visited[1] = true;

    for (int i = 1; i <= N; ++i) {
        position[i] = A[position[i - 1]];
        if (visited[position[i]]) {
            cycle_end = i - 1;
            cycle_start = where_is[position[i]];
            break;
        }
        visited[position[i]] = true;
        where_is[position[i]] = i;
        // cout << position[i] << " " << where_is[position[i]] << '\n';
    }
    // cout << '\n';

    // cout << cycle_start << " " << cycle_end << '\n';

    // int steps = K % cycle_length;
    // cout << position[steps];

    if (K <= cycle_end) {
        cout << position[K] << '\n';
        return 0;
    }

    int steps = (K - cycle_start) % (cycle_end - cycle_start + 1);
    cout << position[cycle_start + steps];

    return 0;
}

Measured memory_bytes: 6032
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
# mod = 998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"
INF = 1<<32-1
# INF = 10**18

def main():
    n,x,m = map(int,ipt().split())
    rps = [x]
    ln = [-1]*m
    ln[x] = 0
    nn = x
    rs = 0
    rg = n
    for i in range(1,n):
        nn = (nn**2)%m
        if ln[nn] == -1:
            ln[nn] = i
            rps.append(nn)
        else:
            rs = ln[nn]
            rg = i
            break
    ans = sum(rps[:rs:])
    smsg = sum(rps[rs:rg:])
    rpl = rg-rs
    ans += (n-rs)//rpl*smsg
    ans += sum(rps[rs:rs+(n-rs)%rpl:])

    print(ans)

    return None

if __name__ == '__main__':
    main()


Measured memory_bytes: 72476
#include<stdio.h>
#include<string.h>

#define MAX 1000

int main()
{
	int i,len,count=0;
	char str[MAX];
	while (1)
	{
		scanf("%s", &str);
		len = strlen(str);
		if (0 <= len && len <= 20){
			break;
		}
	}

	for (i = 0; str[i] != '\0';i++){ count++; }
	for (i=count-1; i >= 0; i--){
		printf("%c", str[i]);
	}
	printf("\n");
	return 0;
}

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

// Macros
#define F  first
#define S  second
#define PB push_back

// Rename Datatypes
using ll  = long long;
using ld  = long double;
using pii = pair<int,int>;

// Common Functions
ll fastpow(ll a, ll ex){ ll res = 1; while(ex){ if(ex & 1) res *= a; a *= a; ex >>= 1; } return res; }
ll fastpow(ll a, ll ex, ll m){ a %= m; ll res = 1; while(ex){ if(ex & 1) res = (a*res) % m; a = (a*a) % m; ex >>= 1; } return res; }
ll modinverse(ll a, ll m){ ll m0 = m, y = 0, x = 1; while (a > 1){ ll q = a / m; a %= m; swap(a,m); x -= q*y; swap(x,y); } if(x < 0) x += m0; return x; }

// HELPERS
//  Tedious Grid Movements
vector<pii> moves_grid = { {0,1} , {0,-1} , {1,0} , {-1,0} };
inline bool move_okay(int x, int y, int n, int m) { return 0 <= x and x < n and 0 <= y and y < m; }
//  Remember:
//   * vec.assign() GOOD; vec.resize() BAD
//   * comparator uses <

// Output, Common Containers
template <typename T> ostream& operator << (ostream &os, const vector<T> &v) { for (T i : v) os << i << ' '; return os; }
template <typename T> ostream& operator << (ostream &os, const set<T> &v)    { for (T i : v) os << i << ' '; return os; }
template <typename T, typename S> ostream& operator << (ostream &os, const pair<T,S> &v) { os << "(" << v.F << "=>" << v.S << ") "; return os; }
template <typename T, typename S> ostream& operator << (ostream &os, const map<T,S> &v)  { for (auto i : v) os << i << ' '; return os; }

// Debugging
#ifdef SANYAM1101
	#define trace(args...) do{ cerr << "TRACE ON! (Line: " << __LINE__ << ")\n"; auto _stream = istringstream{string{#args}}; d_f(_stream, args); } while(0)
	void d_f(__attribute__((unused)) istringstream& _stream) {}
	template<typename Head, typename... Tails> void d_f(istringstream& _stream, Head H, Tails... T) { string _name; _stream >> _name; if(_name.back() == ',') _name.pop_back(); cerr << "\t" << _name << " <=> [" << H << "]\n"; d_f(_stream, T...); }
#else
	#define trace(args...)
#endif


// CODE STARTS HERE

void solve(){
	int n;
	cin >> n;

	if(n == 1){
		cout << "Yes\n";
		return;
	}

	int factors = 0;

	for(int i = 9; i >= 2; --i){
		while(n % i == 0){
			factors += 1;
			n /= i;
		}
	}

	if(n > 1) cout << "No\n";
	else cout << (1 <= factors and factors <= 2 ? "Yes" : "No") << "\n";
}

signed main (void){
	// Fast_IO
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	// Set Fixed Notation (default sucks), High Precision for Floating-Point Output
	cout << fixed << setprecision(20);

	// Multiple TCs
	int tt = 1;
	// cin >> tt;
	while(tt--) solve();
}


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

int main() {
 int n;
 cin >> n;
 vector<int> a(n);
  for(int i = 0; i < n; i++){
    cin >> a.at(i);
  }
  sort(a.begin(), a.end());
  int sum = 0;
   for(int i = 0; i < n-1; i++){
    sum += a.at(i);
  }
  if(a.at(n-1) < sum) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
using namespace std;
void io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const double PI=acos(-1.0);
const double eps=1e-6;
const ll mod=1e9+7;
const int inf=0x3f3f3f3f;
const int maxn=2*1e5+10;
const int maxm=100+10;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int h[maxn];
int dp[maxn];
int main()
{
	io();
	int N,K;cin>>N>>K;
	for(int i = 1;i <= N;++i)
		cin>>h[i];
	dp[1] = 0;
	dp[2] = abs(h[2] - h[1]);
	for(int i = 3;i <= N; ++i){
		dp[i]=dp[i-1]+abs(h[i]-h[i-1]);
		for(int j=max(1,i-K);j<i;++j)
			dp[i]=min(dp[i],dp[j]+abs(h[i]-h[j]));
	}
	cout<< dp[N] <<endl;
	// cout<<ans<<endl;
}


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

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

    int n;
    cin >> n;
    vector<int> a(n);
    pair<int, int> x, y;

    rep(i, 0, n) {
        cin >> a[i];
        if (x.first <= a[i]) {
            y = x;
            x.first = a[i];
            x.second = i;
        } else if (y.first <= a[i]) {
            y.first = a[i];
            y.second = i;
        }
    }

    rep(i, 0, n) {
        if (i != x.second)
            cout << x.first << endl;
        else
            cout << y.first << endl;
    }

    return 0;
}


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

using namespace std;


string s;
string t;
int dp[3010][3010];

int solve(int i, int j){
	if(i == 0 || j == 0)	return dp[i][j] = 0;
	
	if(dp[i][j] != -1)      return dp[i][j];
	
	return dp[i][j] = max(solve(i-1,j),max(solve(i,j-1),(s[i-1] == t[j-1]) + solve(i-1,j-1)));	
}	

string recover(int i, int j){
	if(i == 0 || j == 0){
		return "";
	}
	int val = (s[i-1] == t[j-1]);
	if(dp[i][j] == dp[i-1][j]){
		return recover(i-1,j);
	}else if(dp[i][j] == dp[i][j-1]){
		return recover(i,j-1);
	}else if(dp[i][j] == dp[i-1][j-1] + val){
		return recover(i-1,j-1) + s[i-1]  ;
	}
}

int main(){
	cin >> s >> t;
	memset(dp,-1,sizeof dp);
	solve(s.size(),t.size());
	cout << recover(s.size(),t.size()) << endl;
	return 0;
}


Measured memory_bytes: 36224
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort((c).begin(), (c).end())
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl;
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

using namespace std;



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

    int d, g;
    cin >> d >> g;

    vector<int> p_vec;
    vector<int> c_vec;
    int p, c;
    REP(_, d){
        cin >> p >> c; 
        p_vec.PB(p);
        c_vec.PB(c);
    }

    int res = accumulate(ALL(p_vec), 0);

    // {0, 1, ..., n-1} の部分集合の全探索
    for (int bit = 0; bit < (1<<d); ++bit){
    int s = 0, num = 0, rest_max = -1;
    for (int i = 0; i < d; ++i){
      if (bit & (1<<i)) {
        s += 100 * (i + 1) * p_vec[i] + c_vec[i];
        num += p_vec[i];
      }
      else
        rest_max = i;
    }
    if (s < g){
      int s1 = 100 * (rest_max + 1);
      int need = (g - s + s1 - 1) / s1;
      if (need >= p_vec[rest_max])
        continue;
      num += need;
    }
    res = min(res, num);
  }

    cout << res << '\n';
}


Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <deque>
#include <utility>

int digit[200005][24];

int main(){
  int N;
  scanf("%d", &N);
  std::vector<int > A(N);
  for (int i=0; i<N; i++){
    scanf("%d", &A[i]);
  }
  for (int i=0; i<N; i++){  
    for (int j=0; j<24; j++){
      digit[i][j]=A[i]%2;
      A[i] = A[i]/2;
    }
  }
  int sum[24];
  for (int j=0; j<24; j++){
    sum[j]=0;
  }
  int max=0;
  int r=0; 
  int l=0;
  long long ans=0;
  while (r<N){
    max=0;
    for (int j=0; j<24; j++){
      sum[j]+=digit[r][j];
      max=std::max(max, sum[j]);
    }
    r++;
    if (max<=1){
      ans+=r-l;
    } else {
      while(max>1){
	max=0;
	for (int j=0; j<24; j++){
	  sum[j] -=  digit[l][j];
	  max=std::max(max, sum[j]);
	}
	l++;
      }
      ans+=r-l;
    }
  }
  std::cout << ans << std::endl;
  return 0;
}

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

typedef long long ll;
typedef long double lld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef set<int> si;
typedef map<string, int> msi;
typedef pair<ll, ll> pll;
typedef pair<ll, pair<ll, ll>> plll;

void solve()
{
  ll n;
  cin >> n;
  ll a, b, c, d;
  a = b = c = d = 0;
  for (int i = 0; i < n; i++)
  {
    string s;
    cin >> s;
    if (s == "AC")
      a++;
    if (s == "WA")
      b++;
    if (s == "TLE")
      c++;
    if (s == "RE")
      d++;
  }
  cout << "AC x " << a << endl;
  cout << "WA x " << b << endl;
  cout << "TLE x " << c << endl;
  cout << "RE x " << d << endl;
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  // int t;
  // cin >> t;
  // for (int i = 0; i < t; i++)
  // {
  //   solve();
  // }
  solve();
}

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

using namespace std;
using ll=long long;
using vi=vector<int>;

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    int N , L;
    cin >>N >> L;
    vi a(N);
    for(int i = 0; i < N; i++)
        cin >> a[i];
        int id = -1;
    for(int i = 0; i < N - 1; i++)
    {
        if(a[i] + a[i + 1] >= L){
            id = i  + 1 ;
            break;
        }
    }
    if(id == -1){
        cout << "Impossible" << '\n'; return 0;
    }
    cout<< "Possible" << '\n';

    for(int i = 1; i < id; i++){
        cout << i << '\n';
    }
    for(int i = N - 1; i > id; i--){
        cout << i << '\n';
    }
    cout << id << '\n';
    return 0;
}













Measured memory_bytes: 1280
class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n + 1)]
        self.rank = [0 for _ in range(n + 1)]
        self.size = [1] * (n + 1)
        self.group = [[i] for i in range(n + 1)]

    def find(self, x):
        # If x is root
        if self.parent[x] == x:
            return x
        # If x is not root, search again by using x's parent
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        # Make an edge from the root of lower tree to the root of higher tree
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            # If the height of tree the tree is the same, increase one of the heights by 1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def check_same(self, x, y):
        return self.find(x) == self.find(y)

    def get_size(self, x):
        return self.size[self.find(x)]

    def merge(self, x, y):
        """
        "データ構造をマージする一般的なテク"
        """
        x = self.find(x)
        y = self.find(y)
        if len(self.group[x]) < len(self.group[y]):
            x, y = y, x
        self.group[x].extend(self.group[y])
        self.group[y] = []
        self.parent[y] = x

N, M = map(int, input().split())
items = []
for i in range(M):
    items.append(tuple(map(int, input().split())))

items = list(reversed(items))
uf = UnionFind(N)
ans = N * (N - 1) // 2
minus = 0
res = []

for a, b in items:
    ans -= minus
    res.append(ans)
    if uf.check_same(a, b):
        minus = 0
    else:
        minus = uf.get_size(a) * uf.get_size(b)
    uf.union(a, b)

for r in res[::-1]:
    print(r)


Measured memory_bytes: 38536
import math

class Point:
    def __init__(self, a, b):
        self.x = a
        self.y = b

def koch(n, a, b):
    if n == 0:
        return 0

    s = Point(0, 0)
    t = Point(0, 0)
    u = Point(0, 0)
    th = math.pi * 60.0 / 180

    s.x = (2.0 * a.x + b.x) / 3
    s.y = (2.0 * a.y + b.y) / 3
    t.x = (a.x + 2.0 * b.x) / 3
    t.y = (a.y + 2.0 * b.y) / 3
    u.x = (t.x - s.x) * math.cos(th) - (t.y - s.y) * math.sin(th) + s.x
    u.y = (t.x - s.x) * math.sin(th) + (t.y - s.y) * math.cos(th) + s.y

    koch(n - 1, a, s)
    print("{:.6f} {:.6f}".format(s.x, s.y))
    koch(n - 1, s, u)
    print("{:.6f} {:.6f}".format(u.x, u.y))
    koch(n - 1, u, t)
    print("{:.6f} {:.6f}".format(t.x, t.y))
    koch(n - 1, t, b)

    return 0

a = Point(0.0, 0.0)
b = Point(100.0, 0.0)

n = int(input())

print("{:.6f} {:.6f}".format(a.x, a.y))
koch(n, a, b)
print("{:.6f} {:.6f}".format(b.x, b.y))

Measured memory_bytes: 7972
#[macro_use]
mod input {

use std;
use std::io;

const SPLIT_DELIMITER: char = ' ';

#[macro_export]
#[allow(unused_macros)]
macro_rules! input {
    ( $($x:expr ),*) => {
        {
            let temp_str = input_line_str();
            let mut split_result_iter = temp_str.split_whitespace();
                $(
                let buf_split_result = split_result_iter.next();
                let buf_split_result = buf_split_result.unwrap();
                    ($x) = buf_split_result.parse().unwrap();
                )*
        }
    };
}

#[allow(dead_code)]
pub fn input_line_str() -> String {
    let mut s = String::new();
    io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

#[allow(dead_code)]
pub fn p<T>(t: T)
where
    T: std::fmt::Display,
{
    println!("{}", t);
}

#[allow(dead_code)]
pub fn input_vector2d<T>(line: usize) -> Vec<Vec<T>>
where
    T: std::str::FromStr,
{
    let mut v: Vec<Vec<T>> = Vec::new();

    for _ in 0..line {
        let vec_line = input_vector();
        v.push(vec_line);
    }
    v
}

#[allow(dead_code)]
pub fn input_vector<T>() -> Vec<T>
where
    T: std::str::FromStr,
{
    let mut v: Vec<T> = Vec::new();

    let s = input_line_str();
    let split_result = s.split(SPLIT_DELIMITER);
    for z in split_result {
        let buf = match z.parse() {
            Ok(r) => r,
            Err(_) => panic!("Parse Error"),
        };
        v.push(buf);
    }
    v
}

#[allow(dead_code)]
pub fn str2vec(s: &str) -> Vec<char> {
    let mut v: Vec<char> = Vec::new();
    for c in s.chars() {
        v.push(c);
    }
    v
}

}

use input::*;
use std::collections::BTreeSet;

fn main() {
    let (a, b, k): (isize, isize, isize);
    input!(a, b, k);
    let mut map = BTreeSet::new();
    for z in a..a + k {
        map.insert(z);
    }
    for z in b - k + 1..b + 1 {
        map.insert(z);
    }
    for z in map {
        if a <= z && z <= b {
            p(z);
        }
    }
}

Measured memory_bytes: 4352
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    static public void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        int X = sc.nextInt();
        int M = sc.nextInt();
        Set<Integer> used = new HashSet<>();
        ArrayList<Integer> A = new ArrayList<>();
        A.add(X);
        used.add(X);

        long K=0;
        long L=0;
        long ans = 0;
        boolean breakflag = false;

        for(int i = 0 ; i < M-1 && i < N-1 ; i++){
            long prev  = (long)A.get(i);
            int now = (int)((prev*prev) % M);
            if(now == 0){
                for(int j = 0 ; j <= i ; j++){
                    ans += A.get(j);
                }
                breakflag = true;
                break;
            }else if(used.contains(now)){
                L = i+1;
                for(int j = 0 ; j <= i ; j++){
                    if(A.get(j) == now){
                        K = j;
                        break;
                    }
                    ans += A.get(j);
                }

                long sub = 0;
                for(int j = (int)K ; j < L ; j++){
                    sub += A.get(j);
                }

                long m = (N-K) % (L-K);
                long left = 0;
                for(int j=0; j < m ; j++){
                    left += A.get((int)K + j);
                }

                ans += ((N-K)/(L-K))*sub + left;
                breakflag =true;
                break;
            }else{
                used.add(now);
                A.add(now);
            }
        }

        if(!breakflag){
            ans = 0;
            for(int a:A){
                ans += a;
            }
        }

        System.out.println(ans);
    }
}


Measured memory_bytes: 44188
#include <bits/stdc++.h>
using namespace std;
using lint     = long long;
const lint inf = 1LL << 60;
const lint mod = 1000000007;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    lint q;
    cin >> q;
    deque<string> cs = {"."};
    bool back        = true;
    for (int i = 0; i < q; ++i) {
        int k;
        cin >> k;
        if (k == 1)
            back = !back;
        else if (k == 2) {
            int f;
            string c;
            cin >> f >> c;
            bool fback = f == 2;
            if (back == fback)
                cs.push_back(c);
            else
                cs.push_front(c);
        }
    }
    string ret;
    for (auto &c : cs) {
        if (c == ".")
            ret += s;
        else
            ret += c;
    }
    if (!back)
        reverse(ret.begin(), ret.end());
    cout << ret << "\n";
    return 0;
}

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

using namespace std;

int main(void) {
  string S; cin >> S;

  int ans = 0;
  for (int i = 1; i < S.size(); i++) {
    if (S[i] != S[i-1]) {
      ans++;
    }
  }

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

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

#define M 1000000007
#define MM 998244353 
#define ll long long 
#define pb push_back
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define memf(a) memset(a,false,sizeof(a))
#define all(v) v.begin(),v.end()
#define sz(a) (ll)a.size()
#define F first
#define S second
#define PI 3.1415926536
#define INF 2e18
#define endl "\n"
#define llevel 20
ll power(ll b,ll e,ll m)
{
	if(e==0) return 1;
	if(e&1) return b*power(b*b%m,e/2,m)%m;
	return power(b*b%m,e/2,m);
}
ll power( ll b, ll e)
{
	if(e==0) return 1;
	if(e&1) return b*power(b*b,e/2);
	return power(b*b,e/2);
}

int _runtimeTerror_()
{
	ll k,n;
	cin>>k>>n;
	ll a[n],i;
	for(i=0;i<n;++i)cin>>a[i];
	ll ans=k-a[n-1]+a[0];
	for(i=1;i<n;++i)
		ans=max(ans,a[i]-a[i-1]);
	cout<<k-ans;
	return 0;
}

int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	#ifdef runSieve
		sieve();
	#endif
	#ifdef NCR
		initialize();
	#endif
	int TESTS=1;
	//cin>>TESTS;
	while(TESTS--)
		_runtimeTerror_();
	return 0;
}


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

int main(void) {
    int a, b, c;
    set<int> se;

    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> a;
    cin >> b;
    cin >> c;
    se.insert(a);
    se.insert(b);
    se.insert(c);
    cout << se.size() << "\n";
    return 0;
}

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

typedef pair<int, int> P;

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    for (int i = 0; i < N; i++)
        cin >> A[i];
    vector<int> B(M), C(M);
    for (int i = 0; i < M; i++)
        cin >> B[i] >> C[i];

    priority_queue<P> q;
    for (int i = 0; i < N; i++)
        q.push(P(A[i], 1));
    for (int i = 0; i < M; i++)
        q.push(P(C[i], B[i]));

    long long res = 0;
    for (int i = 0; i < N; i++) {
        P p = q.top(); q.pop();
        res += p.first;
        p.second--;
        if (p.second > 0)
            q.push(p);
    }
    cout << res << endl;
    return 0;
}


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

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

    int N; cin >> N;

    pair<pair<string, int>, int> p[110];

    rep(i,N) {
        string S;
        int P;
        cin >> S >> P;

        p[i] = make_pair(make_pair(S, -P), i);
    }

    sort(p, p + N);

    for (int i = 0; i < N; i++) cout << p[i].second + 1 << endl;
    
    return 0;
}


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

using namespace std;

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define all(c) c.begin(), c.end()
#define rall(c) c.end(), c.begin()
#define INF (int)1e9
#define MOD 1000000007
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef map<int, int> MPII;
typedef set<int> SETI;

const int mxN = 2e5;
int a[mxN];

int t;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    map<string, int> m;
    string ar[4] = {"AC", "WA", "TLE", "RE"};
    cin >> t;

    while (t--)
    {
        string s;
        cin >> s;
        if (m.find(s) != m.end())
            m[s] += 1;
        else
            m[s] = 1;
    }
    for (int i = 0; i < 4; ++i)
    {
        if (m.find(ar[i]) != m.end())
            cout << ar[i] << " x " << m[ar[i]] << "\n";
        else
            cout << ar[i] << " x 0"
                 << "\n";
    }

    return 0;
}

Measured memory_bytes: 3644
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 400000;

ll fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(ll n, ll k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {

	COMinit();

	int N, K;

	cin >> N >> K;

	for (int i = 1; i <= K; i++) {
		cout << COM(N - K + 1, i)*COM(K - 1, i - 1) % MOD << endl;
	}

	

	system("PAUSE");

}

Measured memory_bytes: 9848
import heapq

n, m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)

for i in range(m):
    tmp_min = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-tmp_min//2))
print(-sum(a))

Measured memory_bytes: 14380
n = int(input())
s_1 = input()
word_list = [s_1]
target = s_1[-1]
frag = "Yes"
for i in range(n-1):
  s = input()
  if s in word_list :
    frag = "No"
  if target == s[0]:
    target = s[-1]
  else:
    frag = "No"
 
  word_list.append(s)
    
print(frag)

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




int main() {
  ll n, m;
  cin >> n >> m;
  vector<vector<ll>> to(n);
  vector<ll> h(n);
  rep(i,n){
    cin>>h[i];
  }

  rep(i,m) {
    ll a, b;
    cin >> a >> b;
    --a; --b;
    to[a].push_back(b);
    to[b].push_back(a);
    //blockは連結と関係ないので普通に1:1の対応
  }
//  vector<ll> used(n);
  ll cnt=0;

  rep(i,n){
    bool chk=true;
    ll now=h[i];

    for(ll t:to[i]){
      ll temp=h[t];
      if (temp>=now)chk=false;
    }

    if (chk==true)cnt++;
    }

cout<<cnt;
}


Measured memory_bytes: 9860
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;
 
int main() {
    ll a, b, c;
    cin >> a >> b >> c;
    ll sum = a + b + c;
    ll x = max({a, b, c});

    if(x%2 == sum%2) {
        out((3*x - sum)/2);
    }
    else {
        out((3*(x+1) - sum)/2);
    }

    re0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){string s;
cin>>s;long long n,i,j,p,m=0,r=0;
n=s.size();
for(i=0;i<n;i++){
    if(s[i]=='C'){
        j=i;m=1;break;
    }
}if(m==0)
cout<<"No";
else{
    for(i=j;i<n;i++){
        if(s[i]=='F'){
            r=1;break;
        }
    }if(r==1)
    cout<<"Yes";
    else
    cout<<"No";
}



  return 0;
  
}


Measured memory_bytes: 256
#include <iostream>

using namespace std ;

int main()
{
int x,y,z;
cin>>x>>y>>z;
int t=z-x;
if(t>=0)
{
    if(y-t>=0)
        cout<<"YES";
       else if(y-t<0)
        cout<<"NO";

}
else cout<<"NO";
    return 0;
}


Measured memory_bytes: 256
n = int(input())
if n < 11 or n == 12 or n == 14 or n == 15 or n == 16 or n == 18 or n == 20 or n == 21 or n == 24 or n == 25  or n == 27  or n == 28   or n == 30  or n == 32  or n == 35  or n == 36  or n == 40  or n == 42   or n == 45  or n == 48  or n == 49   or n == 54   or n == 56 or n == 63    or n == 64   or n == 72   or n == 81  :
  print('Yes')
  exit()
print('No')

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

#define int long long
#define ll unsigned long long
#define pb push_back
#define mp make_pair
#define reset(a, b) memset(a, b, sizeof(a))
#define rep(i,b) for(int i=0; i<b; i++)
#define F first 
#define S second
/*----------------------------------------*/


signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int T;
    T=1;
//    cin>>T;

while(T--){
    
    int k;
    cin>>k;
    
    string s;
    cin>>s;
    
    if(s.length()<=k){
        cout<<s;
        continue;
    }
    rep(i,k) cout<<s[i];
    cout<<"...";
}
    
    return 0;
}

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

void dice_roll( int *dice, char i){
	if( i == 'W'){
		int tmp = dice[0];
		dice[0] = dice[1];
		dice[1] = dice[5];
		dice[5] = dice[4];
		dice[4] = tmp;
	}
	if( i == 'S'){
		int tmp = dice[0];
		dice[0] = dice[4];
		dice[4] = dice[5];
		dice[5] = dice[1];
		dice[1] = tmp;
	}
	if( i == 'D'){
		int tmp = dice[0];
		dice[0] = dice[3];
		dice[3] = dice[5];
		dice[5] = dice[2];
		dice[2] = tmp;
	}
	if( i == 'A'){
		int tmp = dice[0];
		dice[0] = dice[2];
		dice[2] = dice[5];
		dice[5] = dice[3];
		dice[3] = tmp;
	}
	if( i == 'd'){
		int tmp = dice[1];
		dice[1] = dice[2];
		dice[2] = dice[4];
		dice[4] = dice[3];
		dice[3] = tmp;
	}
}


int main(){
	/*
		0
	3	1	2	4
		5
	*/
	int dice[6];
	for(int i = 0; i < 6; i++) cin >> dice[i];
	int dice2[6];
	for(int i = 0; i < 6; i++) cin >> dice2[i];
	string s = "No";
	for(int i = 0; i < 4; i++){
		dice_roll(dice2, 'W');
		for(int j = 0; j < 4; j++){
			dice_roll(dice2, 'D');
			for(int k = 0; k < 4; k++){
				dice_roll(dice2, 'd');
				if(dice[0]==dice2[0]&&dice[1]==dice2[1]&&dice[2]==dice2[2]&&dice[3]==dice2[3]&&dice[4]==dice2[4]&&dice[5]==dice2[5])s = "Yes";
			}
		}
	}
	cout << s <<endl;
	return 0;
}



Measured memory_bytes: 3176
#include "bits/stdc++.h"

using namespace std;

typedef long double ld;
typedef long long ll;

#define sz(x) (int)(x).size()
#define pb push_back
#define mp make_pair
#define f first
#define s second

template<typename T, typename U> bool ckmin(T &a, U b){ return b < a ? a = b, true : false; }
template<typename T, typename U> bool ckmax(T &a, U b){ return b > a ? a = b, true : false; }

ll n, res = 0, cnt = 0;
vector<ll> v;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    v.assign(n, 0);
    for(int i = 0; i < n; ++i) cin >> v[i];
    sort(v.begin(), v.end(), greater<ll>());
    res = v[0]; cnt++;
    for(int i = 1; i < n; ++i){
        if(cnt == n - 1) break;
        res += v[i]; cnt++;
        if(cnt == n - 1) break;
        res += v[i]; cnt++;
    }
    cout << res;
    return 0;
}

Measured memory_bytes: 4780
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>

using namespace std;

template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vector<T>>;
using ll = long long;
using ld = long double;

#define REPi(i, s, e) for(int i = (s); i < (e); ++i)
#define REPll(i, s, e) for(ll i = (s); i < (e); ++i)

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

int main()
{
	cin.tie(0);

	ll r, D, x; cin >> r >> D >> x;
	REPi(i, 0, 10)
	{
		x = r * x - D;
		cout << x << endl;
	}

	return 0;
}

Measured memory_bytes: 256
import itertools

n, m, q = map(int, input().split())
lst = []
for _ in range(q):
    item = list(map(int, input().split()))
    lst.append(item)

max_num = 0
for num_lst in itertools.combinations_with_replacement(range(1, m + 1), n):
    count = 0
    for a, b, c, d in lst:
        if num_lst[b - 1] - num_lst[a - 1] == c:
            count += d
    max_num = max(max_num, count)
print(max_num)

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

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,k;
	cin >> n >> k;
	string s;
	cin >> s;
    if (s[k-1] >= 'A' && s[k-1] <= 'Z') {
        int c;
        c = s[k-1] - 'A';
        s[k-1] = c + 'a';
        cout << s;
    }
	return 0;
}

Measured memory_bytes: 3604
#include <algorithm>
#include <bitset>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  string S, T;
  cin >> S >> T;
  vector<vector<int>> cs(26), ct(26);
  for (int i = 0, n = S.size(); i != n; ++i) {
    cs[S[i] - 'a'].push_back(i);
    ct[T[i] - 'a'].push_back(i);
  }

  sort(begin(cs), end(cs));
  sort(begin(ct), end(ct));

  cout << (cs == ct ? "Yes" : "No") << endl;
}


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

using namespace std;

typedef complex<double> Point;
const double PI = acos(-1);

bool cmp(Point a,Point b)
{
    if(a.real()==b.real())
    {
        return a.imag()<b.imag();
    }else
    {
        return a.real()<b.real();
    }
}

Point rotation(Point r,double theta)
{
    double x = r.real(), y = r.imag();
    double c = cos(theta), s = sin(theta);
    return Point(x*c-y*s,x*s+y*c);
}

int main()
{
    double px,py;
    double cx,cy,r;
    cin>>px>>py;
    cin>>cx>>cy>>r;

    Point s(cx-px,cy-py);
    double d = abs(s);
    double theta = PI/2 - acos(r/d);

    Point p(px,py);

    Point t1 = rotation(s,theta);
    Point p1 = p + t1*sqrt(d*d - r*r)/abs(t1);

    Point t2 = rotation(s,-theta);
    Point p2 = p + t2*sqrt(d*d - r*r)/abs(t2);

    if(cmp(p2,p1)) swap(p1,p2);

    cout<<fixed<<setprecision(10);
    cout<<p1.real()<<" "<<p1.imag()<<endl<<p2.real()<<" "<<p2.imag()<<endl;

    return 0;
}



Measured memory_bytes: 3524
N, K = map(int, input().split())
p = list(map(int, input().split()))

P = [(1+p[i])/2 for i in range(N)]

ans = sum(P[:K])
tmp = ans
for i in range(N-K):
    tmp = tmp - P[i]+P[i+K]
    ans = max(ans, tmp)

print(ans)


Measured memory_bytes: 25060
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9+7;


int main(){
  
  int n; cin>>n;
  vector<int> l(n);
  for(auto &i:l) cin>>i;
  int ans{};
  for(int i=0; i<n; i++){
    for(int j=i; j<n; j++){
      for(int k=j; k<n; k++){
        int a = l.at(i);
        int b = l.at(j);
        int c = l.at(k);
        if(a==b||b==c||c==a) continue;
        if(abs(a-b)<c&&c<a+b) ans++;
      }
    }
  }
  cout << ans << endl;
  
}


Measured memory_bytes: 3560
#include <iostream>
#include<algorithm>
#include<queue>
using namespace std;
static const int MAX = 10000;
static const int INFTY = (1<<20);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n;
vector<pair<int, int> > adj[MAX];

void dijkstra(){
    priority_queue<pair<int, int> > PQ;
    int d[MAX],color[MAX];
    for(int i=0; i<n; i++){
        d[i]=INFTY;
        color[i]=WHITE;
    }
    
    d[0]=0;
    PQ.push(make_pair(0, 0));
    color[0]=GRAY;

    
    while (!PQ.empty()) {
        pair<int, int> f = PQ.top(); PQ.pop();
        int u = f.second;
        color[u] = BLACK;
        // 最小値を取り出し、それが最短でなければ無視
        if ( d[u] < f.first * (-1) ) continue;
        
        
        for(int j=0; j<adj[u].size(); j++){
            int v= adj[u][j].first;
            if(color[v]==BLACK) continue;
            if(d[v] > d[u] + adj[u][j].second){
                d[v]=d[u] + adj[u][j].second;
                PQ.push(make_pair(d[v]*(-1),v));
                color[v]=GRAY;
            }
            }
        }
    
    
    for(int i=0; i<n; i++){
      cout << i << " "<< ( d[i] == INFTY ? -1 : d[i] ) << endl;
    }
}



int main(){
    int k, u, v, c;
    
    cin >> n;
    for(int i=0; i<n; i++){
         cin >> u >> k;
        for(int j=0; j<k; j++){
            cin >> v >> c;
             adj[u].push_back(make_pair(v, c));
        }
    }
  
    dijkstra();
    return 0;
    
    
}



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

int main(void)
{
	int a, b, x=0, y=0, z=0;
	cin >> a >> b;
	
	x = a+b;
	y = a-b;
	z = a*b;
	
	if(x>y && x>=z)
		cout << x << endl;
	else if(y>x && y>z)
		cout << y << endl;
	else if(z>x && z>y)
		cout << z << endl;
	else
		cout << x << endl;
		
		
}




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

using namespace std;

#define pb push_back
#define mp make_pair
#define MOD ((int)(1e9) + 7)
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define filename "lynext"
#define freop freopen(filename ".cik","w",stdout);freopen(filename ".gir","r",stdin)
const int N = ((int)1e5) + 5;
const int M = ((int)1e3) + 5;
typedef long long int lli;

int n;
int arr[N];
int narr[N];
int sum;

int main ()
{
	fast;
	//freop;
  cin >> n;
  for (int i = 1; i <= n - 1; i++)
  {
    cin >> arr[i];
  }
  for (int i = 1; i <= n - 1; i++)
    narr[i] = arr[i];
  narr[n] = INT_MAX;
  for (int i = 1; i <= n - 1; i++)
  {
    narr[i + 1] = min(narr[i + 1],arr[i]);
  }
  for (int i = 1; i <= n; i++)
   sum += narr[i];
  cout << sum << "\n";
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

ll dp[2020][2020];
vector<ll> S(2020), T(2020);

ll rec(int i, int j){
	if(dp[i][j] >= 0) return dp[i][j];
	ll res = 0;
	if(i == 0 || j == 0) res = 1;
	else{
		if(S[i-1] == T[j-1]) res += rec(i-1, j-1);
		res += rec(i, j-1);
		res %= mod;
		res += rec(i-1, j);
		res %= mod;
		res -= rec(i-1, j-1);
		res += mod;
		res %= mod;
	}
	dp[i][j] = res;
	return res;
}

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

    ll N, M;
    cin >> N >> M;
    
    REP(i, N) cin >> S[i];
    REP(j, M) cin >> T[j];

    REP(i, 2020)REP(j, 2020) dp[i][j] = -1;

    cout << rec(N, M) << endl;
    return 0;
}

Measured memory_bytes: 32384
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<string>
#define rep(i,n,m) for(int i=(n);i<(int)(m);i++)
#define reps(i,n,m) for(int i=(n);i<=(int)(m);i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define lb lower_bound
#define ub upper_bound
#define LB(a,x) lb(all(a), x) - a.begin()
#define UB(a,x) ub(all(a), x) - a.begin()
#define printfdouble(x) printf("%.12f\n",(x))
#define chartoint(c) (int)((c) - '0')
#define chartoll(c) (long long)((c) - '0')
#define MOD 1000000007
#define itn int
#define enld endl
#define ednl endl
#define icn cin
#define stirng string
using namespace std;
typedef long long ll;
const double pi = 3.141592653589793;
using Graph = vector<vector<int>>;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return 1;} return 0;}
template<class T> bool chmin(T &a, const T &b){if(b<a){a=b; return 1;} return 0;}
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    string s,t; cin >> s >> t;
    int dp[3005][3005];
    int from[3005][3005]; // 1->左上から(文字列追加) 2->左から 3->上から
    Fill(dp, 0);
    Fill(from, 0);
    rep(i,0,SZ(s)){
        rep(j,0,SZ(t)){
            if(s[i] == t[j]){
              chmax(dp[i+1][j+1], dp[i][j] + 1);
            }
            chmax(dp[i+1][j+1], dp[i][j+1]);
            chmax(dp[i+1][j+1], dp[i+1][j]);
        }
    }

    string ans = "";
    int i = SZ(s), j = SZ(t);
    while(i >= 1 && j >= 1){
        if(dp[i][j] == dp[i-1][j]){
            i--;
        }else if(dp[i][j] == dp[i][j-1]){
            j--;
        }else{
            ans += s[i-1];
            i--; j--;
        }
    }

    reverse(all(ans));
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 74188
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main{

    static int[] weightList = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 };

    public static void main(String[] args) {

	Scanner sc = new Scanner(System.in);

	while (sc.hasNextInt()) {
	    int input = sc.nextInt();

	    List<Integer> weights = dividedNumber(input);
	    Collections.sort(weights);
	    StringBuilder sb = new StringBuilder();
	    for (Integer integer : weights) {
		sb.append(integer.toString());
		sb.append(" ");
	    }
	    System.out.println(sb.substring(0, sb.length() - 1));
	}
    }

    private static List<Integer> dividedNumber(double input) {
	List<Integer> weights = new ArrayList<>();
	for (int i = weightList.length - 1; i >= 0; i--) {
	    if (input / (double) weightList[i] == 1d) {
		weights.add(weightList[i]);
		break;
	    }
	    if (input / (double) weightList[i] > 1d) {
		weights = dividedNumber(input % weightList[i]);
		weights.add(weightList[i]);
		break;
	    }
	}
	return weights;
    }

}

Measured memory_bytes: 26216
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using p = pair<int, int>;
#define INF 1001001001
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repX(i, n ,x) for (int i = x; i < (int)(n); i++)
#define repBack(i, n) for (int i = n; i >= 0; i--)
#define dup(x,y) (((x)+(y)-1)/(y))

int main() {
    string S;
    cin >> S;
    if(S=="ABC")cout << "ARC" << endl;
    else cout << "ABC" << endl;

    return 0;
}

Measured memory_bytes: 3624
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
static inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
static inline int lcm(int a, int b) { return a * (b / gcd(a, b)); }

int pow(long x, int n, int m){
    long ret = 1;
    while (n > 0) {
        if (n & 1) ret *= x, ret %= m;
        x *= x, x %= m;
        n >>= 1; 
    }
    return ret % m;
}

int carmichael(int N) {
    int ans = 1;
    if (N % 8 == 0) N /= 2;
    for (int d = 2; d <= N; ++d) {
        if (N % d == 0) {
            int y = d - 1;
            N /= d;
            while (N % d == 0) N /= d, y *= d;
            ans = lcm(ans, y);
        }
    }
    return ans;
}

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

    K /= gcd(K, 7);
    K *= 9;

    int res = carmichael(K);

    if(gcd(K, 10) != 1) {
        printf("%d\n", -1);
        return 0;
    }

    int ans = 1000000;
    for(int i = 1; i * i <= res; ++i){
        if(res % i == 0) {
            if(pow(10, i, K) == 1){
                printf("%d\n", i);
                return 0;
            }
            if(pow(10, res / i, K) == 1) ans = min(ans, res / i);
        }
    }
    printf("%d\n", ans);

    return 0;
}

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

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef unordered_set<int> si;
typedef pair<int, int> pp;
typedef vector<pp> vpp;
typedef unsigned int i64;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#define all(e) (e).begin(), (e).end()
#define pb push_back

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

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


template <typename T>
void printV(vector<T> A) {
  if (A.empty()) cerr << "EMTPY\n";
  else { 
    cerr << "[";
    for (int i = 0; i < A.size() -1 ; ++i) {
      cerr << A[i] << ", ";
    }
    if (A.size()) cerr << A.back() << "]\n";
  }
}


template <typename T>
void printVV(vector<vector<T>> A) {
  cerr << "[";
  for (auto v : A) {
    printV<T>(v);
  }
  cerr << "]";
}

template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << ": " << arg1 << endl;
}

template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&& ...args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

int main(int argc, char **argv) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int a,b; cin >> a >> b;
  cout << a * b << endl;
  return 0;
}



Measured memory_bytes: 3676