akhauriyash/Code-Regression huggingface dataset:
n, m, v, P = gets.chomp.split().map(&:to_i)
a = gets.chomp.split().map(&:to_i)
a.sort!.reverse!

border = a[P-1]
preborder_count = a.select{|e| e>border}.count

ans = 0
bsum = 0
bcount = 0
n.times do |i|
  if a[i] > border
    ans+=1
  elsif a[i] == border
    bsum += a[i]
    bcount += 1
    ans+=1
  else
    if a[i] + m >= border # チャンスあり
      #if n - i + P-1 >= v
      # p [bcount*(a[i]+m), bsum, m*(v-(n - i - 1 + preborder_count))]
      if bcount*(a[i]+m) - bsum >= m*(v-(n - i + preborder_count))
        ans += 1
      end
    end
    bsum += a[i]
    bcount += 1
  end
end

puts ans


Measured memory_bytes: 10248
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

#define MAX_V 2200
int n;
vector<int> g[MAX_V];
int match[MAX_V];
bool used[MAX_V];
void init(int n_) {
	n = n_;
	rep(i, 0, n_)g[i].clear();
}
void addEdge(int u, int v) {
	g[u].emplace_back(v);
	g[v].emplace_back(u);
}
bool augment(int v) {
	used[v] = true;
	for (int u : g[v]) {
		int w = match[u];
		if (w == -1 || (!used[w] && augment(w))) {
			match[v] = u;
			match[u] = v;
			return true;
		}
	}
	return false;
}

int maximumMatching() {
	int cnt = 0;
	memset(match, -1, sizeof(match));
	for (int v = 0; v < n; v++) {
		if (match[v] == -1) {
			memset(used, false, sizeof(used));
			if (augment(v))cnt++;
		}
	}
	return cnt;
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	for (int N, M, L; cin >> N >> M >> L&&N;) {
		vector<vector<int>> g(N, vector<int>(N, INF));
		rep(i, 0, M) {
			int u, v, d; cin >> u >> v >> d;
			g[u][v] = g[v][u] = d;
		}
		rep(i, 0, N)
			g[i][i] = 0;
		rep(k, 0, N)rep(i, 0, N)rep(j, 0, N) {
			if (g[i][k] != INF&&g[k][j] != INF)
				g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
		}

		vector<int> p(L), t(L); rep(i, 0, L) {
			cin >> p[i] >> t[i];
		}
		init(L + L);
		int source = L + L, sink = source + 1;
		rep(i, 0, L) {
			rep(j, 0, L) {
				if (i == j)continue;
				if (g[p[i]][p[j]] <= t[j] - t[i]) {
					addEdge(i, L + j);
				}
			}
		}
		auto ans = L - maximumMatching();
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 11552
using System;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        int[] a = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        int max = 0;
        for (int i = 0; i < a.Length; i++)
            max += a[i] - 1;

        Console.WriteLine(max);
    }
}

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

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

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

	ll N, H; cin >> N >> H;

	ll ma = -1;
	ll b[100005];
	ll a[100005];
	for (int i = 0;i < N;i++){
		cin >> a[i] >> b[i];
		ma = max(ma,a[i]);
	}

	sort(b,b+N); reverse(b,b+N);

	ll idx = 0;
	ll ans = 0;

	while(H > 0){
		if(b[idx] <= ma){
			ans += H/ma;
			if(H%ma != 0) ans++;
			break;
		}
		H -= b[idx];
		idx++;
		ans++;
	}

	cout << ans << endl;

	return 0;

}


Measured memory_bytes: 1792
#pragma GCC optimize("O3") 

#include <bits/stdc++.h>
using namespace std;

typedef long long int           ll;
typedef unsigned long long int  ull;
typedef long double             ld;

typedef pair<int, int>          pii;
typedef pair<ll,ll>             pll;
typedef vector<int>             vi;
typedef vector<ll>              vll;
typedef vector<pii>             vpii;
typedef vector<pll>             vpll;

#define test(t)		        int t; cin >> t; while(t--)
#define f(i, a, b)	        for(int (i) = (a); (i) < (b); ++(i))
#define all(a)		        (a).begin(), (a).end()
#define endl 		        "\n"
#define maxvec(vec)             *max_element(all(vec))
#define minvec(vec)             *min_element(all(vec))
#define maxarr(arr)             *max_element(arr, arr + n)
#define minarr(arr)             *min_element(arr, arr + n)
#define deb(x)		        cout << #x << ": " << x << endl;
#define deb2(x,y)	        cout << #x << ": " << x << " ~ " <<  #y << ": " << y << endl;
#define deba(arr)	        cout << #arr << " ~ [ "; for(auto n: arr) cout << n << " "; cout << "]" << endl;
#define debap(arr)	        cout << #arr << " ~ [ "; for(auto n: arr) cout << n.first << "-" << n.second << " "; cout << "]" << endl;
#define fast 		        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

#define mx9		1000000007
#define mx7		10000007
#define mx6		1000006
#define mx5		200005
#define inf		1<<30                                 
#define eps		1e-9
#define mod		1000000007
#define PI		3.141592653589793238462643383279502884L

void solve()
{
    ll n, ct = 0;
    ld d;
    cin >> n >> d;
    f(i, 0, n)
    {
        ld x, y;
        cin >> x >> y;
        ld t = (sqrt((x * x)+ (y * y)));
        // deb2(t, d)
        if(t <= d)
            ct += 1;
    }
    cout << ct << endl;
}

int main()
{
    fast;
    // test(t)
        solve();
    return 0;
}

Measured memory_bytes: 3800
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, [ $t:tt ]) => {{
        let len = read_value!($next, usize);
        (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    }};

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused)]
macro_rules! debug {
    ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap());
}
#[allow(unused)]
macro_rules! debugln {
    ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap());
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (let _ = write!(out,$($format)*););
    }
    input! {
        n: usize,
        a: [i64; n],
    }
    let mut tot: i64 = 0;
    let mut hm = HashMap::new();
    for i in 0..n {
        let val = i as i64 - a[i];
        tot += *hm.get(&val).unwrap_or(&0);
        *hm.entry(a[i] + i as i64).or_insert(0) += 1;
    }
    puts!("{}\n", tot);
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 9208
#include "bits/stdc++.h"
using namespace std;
using ll = int64_t; using pii = pair<int, int>;
const int MOD = (int)1e9 + 7, INF = (1 << 27); const ll INFLL = (1LL << 55);
#define FOR(i,a,b) for(int (i)=(a);(i)<(int)(b);(i)++)
#define rep(i,n) FOR(i,0,n)
template<typename T, typename U> inline void chmax(T &x, U y) { if (x < y) x = y; }
template<typename T, typename U> inline void chmin(T &x, U y) { if (x > y) x = y; }


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

	int ma = min(a, b);
	int mi = max(0, a + b - n);
	cout << ma << " " << mi << endl;
}

Measured memory_bytes: 256
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<LL, LL>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vector<P> l, r;
    rep(i, N){
        LL a, b;
        scanf("%lld %lld", &a, &b);
        l.pb({a, b});
        r.pb({b, a});
    }
    
    // 2. sort.
    sort(all(l));
    sort(all(r));
    
    // 3. 中央値の範囲を推定.
    LL ans = 1;
    int n = N / 2;
    if(N & 1) ans += r[n].a - l[n].a;
    else      ans += (r[n].a - l[n].a) + (r[n - 1].a - l[n - 1].a);
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

Measured memory_bytes: 9856
#include <bits/stdc++.h>
#define ll long long
#define rep(X,N) for(int X = 0; X < N; X++)
#define PI (acos(-1.0))
#define sorta(V) sort(V.begin(), V.end())
#define pback push_back
#define mpair make_pair

using namespace std;

int main(){

    char tmp[5];
    cin >> tmp;

    bool h = false;
    int num = atoi(tmp);

    int a = num / 1000;
    int b = (num / 100) % 10;
    int c = (num / 10) % 10;
    int d = num % 10;

    int i,j,k;

    for(i = -1; i < 2; i = i + 2){
        for(j = -1; j < 2; j = j + 2){
            for(k = -1; k < 2; k = k + 2){
                if(a + i * b + j * c + k * d == 7){
                    h = true;
                    i++;
                    j++;
                    k++;
                    cout << tmp[0] << (i ? "+" : "-") << tmp[1] << (j ? "+" : "-") << tmp[2] << (k ? "+" : "-") << tmp[3] << "=7" << endl;
                    break;
                }
            }
            if(h) break;
        }
        if(h) break;
    }
    
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  char s;
  cin>>s;
  if(s=='a')
  {
      cout<<"b"<<endl;
  }
  else if(s=='b')
  {
      cout<<"c"<<endl;
  }
   else if(s=='c')
  {
      cout<<"d"<<endl;
  }
   else if(s=='d')
  {
      cout<<"e"<<endl;
  }
   else if(s=='e')
  {
      cout<<"f"<<endl;
  }
   else if(s=='f')
  {
      cout<<"g"<<endl;
  }
   else if(s=='g')
  {
      cout<<"h"<<endl;
  }
   else if(s=='h')
  {
      cout<<"i"<<endl;
  }
   else if(s=='i')
  {
      cout<<"j"<<endl;
  }
   else if(s=='j')
  {
      cout<<"k"<<endl;
  }
   else if(s=='k')
  {
      cout<<"l"<<endl;
  }
   else if(s=='l')
  {
      cout<<"m"<<endl;
  }
   else if(s=='m')
  {
      cout<<"n"<<endl;
  }
   else if(s=='n')
  {
      cout<<"o"<<endl;
  }
   else if(s=='o')
  {
      cout<<"p"<<endl;
  }
   else if(s=='p')
  {
      cout<<"q"<<endl;
  }
   else if(s=='q')
  {
      cout<<"r"<<endl;
  }
   else if(s=='r')
  {
      cout<<"s"<<endl;
  }
   else if(s=='s')
  {
      cout<<"t"<<endl;
  }
   else if(s=='t')
  {
      cout<<"u"<<endl;
  }
   else if(s=='u')
  {
      cout<<"v"<<endl;
  }
   else if(s=='v')
  {
      cout<<"w"<<endl;
  }
   else if(s=='w')
  {
      cout<<"x"<<endl;
  }
   else if(s=='x')
  {
      cout<<"y"<<endl;
  }
   else if(s=='y')
  {
      cout<<"z"<<endl;
  }
  return 0;
}


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

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

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

    sort(a.begin(), a.end()); // 降順（大きい順）でソー
    int ans = 0;

    for (int i = 0; i < N; i++)
    {
        if (i < N - 1)
        {
            if(a[i]==a[i+1]){
                i++;
            }else{
                ans++;
            }
        }
        else
        {
            if (a[i] != a[i - 1]){
                ans++;
            }else if(a[i]==a[i-2]){
                ans++;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3160
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;

typedef long long ll;
typedef pair<int, int> Pii;

void readline(int N, vector<int> &a){
    string s;
    for(int i = 0; i < N - 1; i++){
        getline(cin, s, ' ');
        a[i] = atoi(s.c_str());
    }
    getline(cin, s, '\n');
    a[N - 1] = atoi(s.c_str());
}
void readline(int N, vector<double> &a){
    string s;
    for(int i = 0; i < N - 1; i++){
        getline(cin, s, ' ');
        a[i] = atof(s.c_str());
    }
    getline(cin, s, '\n');
    a[N - 1] = atof(s.c_str());
}

int main(){

    vector<int> A(3);
    readline(3, A);

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

    cout << A[2] - A[0];

    return 0;    
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		while(scan.hasNext()){
			Long m = scan.nextLong();
			Long n = scan.nextLong();
			Long g = gcd(m, n);
			System.out.println(g+" "+(m*n/g));
		}
	}
	
	private static Long gcd(Long a, Long b){
		return (b == 0)? a:gcd(b, a%b);
	}
}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  long long int n, m, x;
  cin >> n >> m >> x;
  long long int ans = 1e9+7;
  long long int ca[n][m+1];
  for(int i=0; i<n; i++){
    for(int j=0; j<m+1; j++){
      cin >> ca[i][j];
    }
  }
  int step = 1;
  step <<= n;
  for(int i=1; i<step; i++){
    long long int tmp[m+1] = {};
    int g = 0;
    bool ok = true;
    while(g<n){
      if(i & (1<<g)){
        for(int j=0; j<=m; j++){
          tmp[j] += ca[g][j];
        }
      }
      g++;
    }
    for(int j=1; j<=m; j++){
      if(tmp[j] >= x) continue;
      ok = false;
    }
    if(ok){
      ans = min(ans, tmp[0]);
    }
  }
  if(ans == 1e9+7) ans = -1;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3624
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

ll dx[9] = {-1,0,1,-1,0,1,-1,0,1};
ll dy[9] = {-1,-1,-1,0,0,0,1,1,1};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll h, w, n;
	cin >> h >> w >> n;
	map<P,ll> mp;
	rep(i,n){
		ll a, b;
		cin >> a >> b;
		--a; --b;
		rep(j,9){
			ll nx = b + dx[j];
			ll ny = a + dy[j];
			if(nx <= 0 || w-1 <= nx) continue;
			if(ny <= 0 || h-1 <= ny) continue;
			mp[P(ny, nx)]++;
		}
	}
	vector<ll> ans(10, 0);
	ans[0] = (h-2)*(w-2);
	for(auto p : mp){
		ans[p.second]++;
		ans[0]--;
	}
	rep(i,10){
		cout << ans[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 56576
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = 200000;
        int[] b = new int[n];
        int[] a = new int[m+1];

        for(int i=0; i<n; i++) {
            b[i] = sc.nextInt();
            a[b[i]]++;
        }
        long sum = 0;
        for(int i=1; i<m; i++) {
            sum += ((long)a[i] * (a[i]-1) / 2);
        }

        for(int i=0; i<n; i++) {
            int num = b[i];
            long res = sum - (long)a[num] * (a[num]-1) / 2 + (long)(a[num]-1) * (a[num]-2) / 2;
            System.out.println(res);
        }
    }


}

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

#define CIN_ONLY if(1)
struct cww{cww(){
    CIN_ONLY{
        ios::sync_with_stdio(false);cin.tie(0);
    }
}}star;
#define fin "\n"
#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define DEBUG if(0)
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l,T r)
{bool a=l>r;if(a)l=r;return a;}
template <typename T>inline bool chmax(T &l,T r)
{bool a=l<r;if(a)l=r;return a;}
template <typename T>
istream& operator>>(istream &is,vector<T> &v){
    for(auto &it:v)is>>it;
    return is;
}
vector<int> res;
int num=1;
void f(LL n){
    if(n<=0)
        return;    
    f((n-1)/2);
    res.push_back(num++);
    if(n&1);
    else res.insert(res.begin(),num++);
}
int main(){
    LL N;
    cin>>N;
    f(N);
    cout<<res.size()*2<<endl<<1;
    FOR(i,2,num)cout<<" "<<i;
    for(auto &it:res)cout<<" "<<it;
    cout<<endl;
    
    return 0;
}


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

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

int main() {
    int n;
    cin >> n;
    vector<ll> a (n);
    for(int i=0; i<n; i++){
        cin >> a.at(i);
    }
    ll g = gcd(a.at(0),a.at(1));
    for(int i=2; i<n; i++){
        g = gcd(a.at(i),g);
    }
    cout << g << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;using ll=long long;using uint=unsigned int;using pii=pair<int,int>;using pll=pair<ll,ll>;using ull = unsigned long long;using ld=long double;template<typename T>void _(const char*s,T h){cerr<<s<<" = "<<h<<"\n";}template<typename T,typename...Ts>void _(const char*s,T h,Ts...t){int b=0;while(((b+=*s=='(')-=*s==')')!=0||*s!=',')cerr<<*s++;cerr<<" = "<<h<<",";_(s+1,t...);}// break continue pop_back 998244353
#define int ll
// #define pii pll
#define f first
#define s second
#define pb emplace_back
#define forn(i,n) for(int i=0;i<(n);++i)
#define sz(a)((int)(a).size())
#define sqr(x) ((x)*(x))
struct init{init(){cin.tie(0);iostream::sync_with_stdio(0);cout<<fixed<<setprecision(10);cerr<<fixed<<setprecision(5);}~init(){
#ifdef LOCAL
#define dbg(...) _(#__VA_ARGS__,__VA_ARGS__)
cerr<<"Time elapsed: "<<(double)clock()/CLOCKS_PER_SEC<<"s.\n";
#else
#define dbg(...) 
#endif
}}init;template<typename T,typename U>void upx(T&x,U y){if(x<y)x=y;}template<typename T,typename U>void upn(T&x,U y){if(x>y)x=y;}mt19937 rng(12);const int D=4,dx[]={+1,0,-1,0},dy[]={0,+1,0,-1};
const int N=3e5+5;
pii a[N];
pii as[N];
int u[N];
int32_t main(){
    int n;
    cin>>n;
    forn(i,n)cin>>a[i].s;
    forn(i,n)cin>>a[i].f;
    sort(a,a+n);
    forn(i,n)as[i]={a[i].s,i};
    sort(as,as+n);
    int ok=1;
    forn(i,n)ok&=as[i].f<=a[i].f;
    if(!ok){
        cout<<"No\n";
        return 0;
    }
    int cyc=0;
    forn(i,n){
        if(!u[i]){
            int v=i;
            do{
                u[v]=1;
                v=as[v].s;
            }while(!u[v]);
            cyc++;
        }
    }
    if(cyc>1){
        cout<<"Yes\n";
        return 0;
    }
    int any=0;
    forn(i,n-1){
        if(as[i+1].f<=a[i].f)any=1;
    }
    if(any)cout<<"Yes\n";
    else cout<<"No\n";

    return 0;
}

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

using namespace std;

namespace {

    typedef double real;
    typedef long long ll;

    template<class T> ostream& operator<<(ostream& os, const vector<T>& vs) {
        if (vs.empty()) return os << "[]";
        os << "[" << vs[0];
        for (int i = 1; i < vs.size(); i++) os << " " << vs[i];
        return os << "]";
    }
    template<class T> istream& operator>>(istream& is, vector<T>& vs) {
        for (auto it = vs.begin(); it != vs.end(); it++) is >> *it;
        return is;
    }

    int N;
    vector<int> P;
    bool input() {
        cin >> N;
        if (N == 0) return false;
        P.clear(); P.resize(N); cin >> P;
        return true;
    }

    struct Pair : pair<int,int> {
        Pair(int a, int b) : pair<int,int>(a, b) {}
    };

    const int INF = 1<<28;
    bool operator<(const Pair& a, const Pair& b) {
        if (a.first == b.first) return a.second > b.second;
        return a.first < b.first;
    }
    Pair max(const Pair& a, const Pair& b) {
        return (b < a ? a : b);
    }

    const int MAX_R = 101 * 500 + 5;

    void solve() {
        vector<vector<Pair>> dp(N + 1, vector<Pair>(MAX_R, Pair(-INF, INF)));
        dp[0][0] = Pair(0, 0);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < MAX_R; j++) {
                const auto& cur = dp[i][j];
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
                int p = P[i] % 1000;
                if (p == 0) {
                    if (j >= 500) {
                        auto& next = dp[i + 1][j - 500];
                        next = max(next, Pair(dp[i][j].first + 1, dp[i][j].second + P[i]));
                    }
                } else if (p <= 500) {
                    int nrem = j + (1000 - p) % 500;
                    auto& next = dp[i + 1][nrem];
                    next = max(next, Pair(cur.first + 1, cur.second + P[i]));
                } else {
                    int d = p % 500;
                    if (j >= d) {
                        auto& next = dp[i + 1][j - d];
                        next = max(next, Pair(cur.first + 1, cur.second + P[i]));
                    } else {
                        auto& next = dp[i + 1][j + 1000 - p];
                        next = max(next, Pair(cur.first, cur.second + P[i]));
                    }
                }
            }
        }
        auto ans = Pair(-INF, INF);
        for (int i = 0; i < MAX_R; i++) {
            ans = max(ans, dp[N][i]);
        }
        cout << ans.first << " " << ans.second << endl;
    }
}

int main() {
    while (input()) solve();
    return 0;
}

Measured memory_bytes: 43188
// hloya template v24

// ░░░░░░░▄▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄░░░░░░
// ░░░░░░█░░▄▀▀▀▀▀▀▀▀▀▀▀▀▀▄░░█░░░░░
// ░░░░░░█░█░▀░░░░░▀░░▀░░░░█░█░░░░░
// ░░░░░░█░█░░░░░░░░▄▀▀▄░▀░█░█▄▀▀▄░
// █▀▀█▄░█░█░░▀░░░░░█░░░▀▄▄█▄▀░░░█░
// ▀▄▄░▀██░█▄░▀░░░▄▄▀░░░░░░░░░░░░▀▄
// ░░▀█▄▄█░█░░░░▄░░█░░░▄█░░░▄░▄█░░█
// ░░░░░▀█░▀▄▀░░░░░█░██░▄░░▄░░▄░███
// ░░░░░▄█▄░░▀▀▀▀▀▀▀▀▄░░▀▀▀▀▀▀▀░▄▀░
// ░░░░█░░▄█▀█▀▀█▀▀▀▀▀▀█▀▀█▀█▀▀█░░░
// ░░░░▀▀▀▀░░▀▀▀░░░░░░░░▀▀▀░░▀▀░░░░

#include <bits/stdc++.h>
#include <valarray>
using namespace std;

bool dbg = 0;

clock_t start_time = clock();
#define current_time fixed<<setprecision(6)<<(ld)(clock()-start_time)/CLOCKS_PER_SEC

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()

#define ll long long
#define ld long double
#define pii pair<int,int>
#define umap unordered_map<int, int>

#define files1 freopen("input.txt","r",stdin)
#define files2 freopen("paths.out","w",stdout)
#define files files1;files2
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0)

#define endl '\n'
#define ln(i,n) " \n"[(i) == (n) - 1]

void bad(string mes = "Impossible"){cout << mes;exit(0);}
void bad(int mes){cout << mes;exit(0);}

template<typename T>
string bin(T x, int st = 2){
    string ans = "";
    while (x > 0){
        ans += char('0' + x % st);
        x /= st;
    }
    reverse(ans.begin(), ans.end());
    return ans.empty() ? "0" : ans;
}

template<typename T>
void amax(T& x, T y) {
    x = max(x, y);
}

template<typename T>
void amin(T& x, T y) {
    x = min(x, y);
}

template<typename T>
T input(){
    T ans = 0, m = 1;
    char c = ' ';

    while (!((c >= '0' && c <= '9') || c == '-')) {
        c = getchar();
    }

    if (c == '-')
        m = -1, c = getchar();
    while (c >= '0' && c <= '9'){
        ans = ans * 10 + (c - '0'), c = getchar();
    }
    return ans * m;
}

template<typename T> void read(T& a) { a = input<T>(); }
template<typename T> void read(T& a, T& b) { read(a), read(b); }
template<typename T> void read(T& a, T& b, T& c) { read(a, b), read(c); }
template<typename T> void read(T& a, T& b, T& c, T& d) { read(a, b), read(c, d); }

const int inf = 2e9 + 20;
const short short_inf = 3e4 + 20;
const long double eps = 1e-12;
const int maxn = 1e5 + 12, base = 1e9 + 7;
const ll llinf = 2e18 + 5;

template<typename T>
T binpow(T n, T s)
{
    if (s <= 0)
        return 1LL;
    if (s % 2 == 0){
        T b = binpow(n, s / 2);
        return ( 1LL * b * b ) % base;
    } else {
        return (1LL* binpow(n, s - 1) * n) % base;
    }
}

int a[maxn];
ll ans[maxn];

int main() {
    int n;
    read(n);

    vector<pii> kek;
    for (int i = 0; i < n; i++) {
        read(a[i]);
        kek.pb(mp(a[i], -i));
    }
    sort(all(kek));
    reverse(all(kek));

    int mn_in_set = -kek[0].s, x = kek[0].f;
    for (int i = 1; i < n; i++) {
        int y = kek[i].f, curIt = -kek[i].s;
        ans[mn_in_set] += 1ll * i * (x - y);
        x = y;
        amin(mn_in_set, curIt);
        // cnt
    }
    ans[mn_in_set] += 1ll * n * x;
    for (int i = 0; i < n; i++)
        cout << ans[i] << endl ;
    return 0;
}

Measured memory_bytes: 3188
//start 2020 13:17
//end 2020 13:
/*
学んだこと
C++の動的配列はvectorによって可能である。
*/
//C - Traveling Salesman around Lake
#include <vector>
#include<iostream>
using namespace std;

int main(){
  int K,N;
  int box;
    cin >> K;
    cin >> N;
    vector<int> p(N+1,-1);
    vector<int> route(N,-1);
    for(int i=0;i<N;i++){
      cin >> p[i];
    }
    p[N]=K+p[0];

    for(int i=0;i<N;i++){
      //cout<<"i:"<<i<<"  (i+1)%N:"<<(i+1)%N<<endl;
      if((p[(i+1)] - p[i])>=0){
        route[i]=p[(i+1)] - p[i];
      }else{
        route[i]=p[i]-p[(i+1)];
      }
    }

  int max=-1;
  int pn=-1;
  for(int i=0;i<N+1;i++){
    if(route[i]>max){
      max=route[i];
      pn=i;
    }
  }
  int ans=0;
  //for(int i=0;i<N+1;i++){
    //cout<<p[i]<<' ';
  //}
  //cout<<' '<< endl;
  //for(int i=0;i<N+1;i++){
    //cout<<route[i] << ' ';
  //}
  //cout<<' '<<endl;
  for(int i=0;i<N+1;i++){
    if(i!=pn){
      ans+=route[i];
    }
  }
  cout<<ans;

}


Measured memory_bytes: 1792
package main

import ("fmt")

func main() {
	var number int
	var text, text2 string

	fmt.Scan(&number, &text, &text2)

	var ans string
	for i := 0; i < number; i++ {
		ans += string(text[i])
		ans += string(text2[i])
	}

	fmt.Println(ans)
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define M (1000000007)
#define N (100010)
int a;
char s[1000];

int main(){
	scanf("%d",&a);
	scanf("%s",s);
	if (a>=3200) printf("%s",s);
	else printf("red");
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  int n,A[100],ans=0;
  cin>>n;
  for(int i=0;i<n;i++)cin>>A[i];
  for(int i=0;i<n-1;i++){
    for(int j=n-1;j>i;j--){
      if(A[j]<A[j-1]){
    swap(A[j],A[j-1]);
    ans++;
      }
    }
  }
  for(int i=0;i<n;i++){
    if(i)cout<<' ';
    cout<<A[i];
  }
  cout<<endl<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3116
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
using namespace std;
using LL = long long;

LL N;
vector<int>graph[123456];
int deg[123456];

map<pair<int, int>, bool>memo;
bool dp(int b, int to) {
	if (memo.count(make_pair(b, to))) {
		return memo[{b, to}];
	}
	if (graph[to].size() == 1) {
		return memo[{b, to}] = true;
	}
	if (graph[to].size() == 2) {
		int other = graph[to][0];
		if (other == b)other = graph[to][1];
		return memo[{b, to}] = dp(to, other);
	}
	return memo[{b, to}] = false;
}

int main(void)
{
	cin >> N;
	for (int i = 1; i < N; ++i) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
		deg[a]++;
		deg[b]++;
	}
	map<int, int>inv;
	for (int i = 0; i < N; ++i) {
		inv[deg[i]]++;
	}
	if (inv[1] == 2 && inv[2] == N - 2) {
		//パス
		cout << 1 << endl;
		return 0;
	}
	int ans = 0;
	for (int i = 0; i < N; ++i) {
		bool part = false;
		int cnt = 0;
		for (int j : graph[i]) {
			cnt += (dp(i, j) ? 1 : 0);
			if (dp(j, i)) {
				part = true;
				break;
			}
		}
		if (part)continue;
		if (cnt) {
			ans += cnt - 1;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 19840
using System;

class ABC_129_B
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());

        string[] input = Console.ReadLine().Split(' ');
        int[] WSum = new int[N];
        int sum = 0;
        for (int i = 0; i < N; i++)
        {
            sum += int.Parse(input[i]);
            WSum[i] += sum;
        }

        int ans = int.MaxValue;
        for (int i = 0; i < N-1; i++)
        {
            int S1 = WSum[i];
            int S2 = WSum[N-1] - S1;

            int abs = Math.Abs(S1 - S2);

            ans = Math.Min(abs, ans);
        }

        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 13140
import java.util.*;
 
public class Main {
	
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	int A = sc.nextInt();
    	int B = sc.nextInt();
    	int H = sc.nextInt();
    	int M = sc.nextInt();
    	double h = 30 * (H + M/60.0);
    	double m = M * 6.0;
    	double k = 360 - Math.abs(m - h);
    	double cos = Math.cos(Math.toRadians(k));
    	double a = A*A + B*B - (2*A*B*cos);
    	System.out.println(Math.sqrt(a));
    }
}

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

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

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

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	int n;
	cin >> n;
	int a[n];
	for (int i = 0; i < n; i++) cin >> a[i];
	
	pair<long long, long long> dp[n][n];
	for (int j = 0; j < n; j++) {
		for (int i = j; i >= 0; i--) {
			if (i == j) dp[i][j] = {a[i], 0};
			else {
				if (dp[i + 1][j].second + a[i] > dp[i][j - 1].second + a[j]) {
					dp[i][j] = {dp[i + 1][j].second + a[i], dp[i + 1][j].first};
				} else {
					dp[i][j] = {dp[i][j - 1].second + a[j], dp[i][j - 1].first};
				}
			}
		}
	}
	cout << dp[0][n - 1].first - dp[0][n - 1].second;
}

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

using namespace std;

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

  bool flag = false;
  if(S[0] == 'A'){
    int cnt = 0;
    for(int i = 2; i<S.length()-1; i++ ){
      if(S[i]=='C') cnt++;
    }
    if(cnt == 1){
      bool f2 = true;
      for(int i = 1; i<S.length(); i++){
        if(S[i] != 'C'){
          if(!(S[i]>='a' && S[i] <= 'z')){
            f2 = false;
          }
        }
      }
      if(f2) flag = true;
    }
  }

  if(flag) cout << "AC";
  else cout << "WA";

  return 0;
}


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

using namespace std;

int main() {
  string s;
  cin >> s;
  
  int n = (int)s.size();
  string t = "KIHBR";
  char prev = s[0];
  string comp = "";
  if (prev != 'A') comp += prev;
  for (int i = 1; i < n; ++i) {
    if (s[i] == 'A' && prev == 'A') {
      puts("NO");
      return 0;
    }
    if ((prev == 'K' && s[i] != 'I') ||(prev == 'I' && s[i] != 'H')){
      puts("NO");
      return 0;
    }
    if (s[i] != 'A') {
      comp += s[i];
    }
    prev = s[i];
  }
  
  if (t.compare(comp) == 0) puts("YES");
  else puts("NO");
  return 0;
}

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

int main()
{
  int n, m;
  cin >> n >> m;
  int i;
  int ans = 0;
  int tim = 100*(n-m)+1900*m;
  for(i = 0; i < m; i++)
  {
    tim *= 2;
  }
  cout << tim << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define ll long long
inline ll read()
{
	ll x=0,w=0;char ch=getchar();
	while(!isdigit(ch))w|=ch=='-',ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return w?-x:x;
}
struct op{int x,y,a,b;}B[400005];
int R,C,n,tot;
inline bool com(op x,op y){return (x.x==y.x)?(x.y<y.y):(x.x<y.x);}
struct BIT
{
    int szsz[400005];
    inline void modify(int x)
    {
        for(reg int i=x+1;i<=400000;i+=i&(-i))szsz[i]++;
    }
    inline int ask(int x)
    {
        reg int res=0;
        for(reg int i=x+1;i;i^=i&(-i))res+=szsz[i];
        return res;
    }
    inline int query(int l,int r)
    {return ask(r)-ask(l-1);}
}xi,xa,yi,ya;
#define No {puts("NO");exit(0);}
inline void bd(int x,int y,int a,int b)
{
    if(x==a&&x==0){if(xi.query(y,b))No;return ;}
    if(x==a&&x==R){if(xa.query(y,b))No;return ;}
    if(y==b&&y==0){if(yi.query(x,a))No;return ;}
    if(y==b&&y==C){if(ya.query(x,a))No;return ;}
    if(x==0&&b==C)
    {
        if(ya.query(0,a))No;
        if(xi.query(y,C))No;return ;
    }
    if(x==0&&b==0)
    {
        if(xi.query(y,C))No;
        if(ya.query(0,R))No;
        if(xa.query(0,C))No;
        if(yi.query(a,R))No;return ;
    }
    if(a==R&&y==C)
    {
        if(xa.query(b,C))No;
        if(ya.query(x,R))No;return ;
    }
    if(a==R&&y==0)
    {
        if(xa.query(0,b))No;
        if(yi.query(x,R))No;return ;
    }
    if((y==0||y==C)&&(b==0||b==C))
    {
        if(xa.query(0,C))No;
        if(y==0)
        {
            if(yi.query(x,R))No;
            if(ya.query(a,R))No;
        }
        else
        {
            if(yi.query(a,R))No;
            if(ya.query(x,R))No;
        }return ;
    }
    if(ya.query(0,R))No;
    if(xi.query(y,C))No;
    if(xa.query(b,C))No;
}
int gs1,gs2,ax[400010],by[400010];
int xx[400010],yy[400010],aa[400010],bb[400010];
int main()
{
    R=read(),C=read(),n=read();
    reg int i,x,y,a,b;
    for(i=1;i<=n;++i)
    {
        xx[i]=read(),yy[i]=read();aa[i]=read(),bb[i]=read();
        ax[++gs1]=xx[i];ax[++gs1]=aa[i];
        by[++gs2]=yy[i];by[++gs2]=bb[i];
    }
    ax[++gs1]=0;ax[++gs1]=R;by[++gs2]=0;by[++gs2]=C;
    sort(ax+1,ax+1+gs1);sort(by+1,by+1+gs2);
    gs1=unique(ax+1,ax+1+gs1)-ax-1;
    gs2=unique(by+1,by+1+gs2)-by-1;
    for(i=1;i<=n;++i)
    {
        xx[i]=lower_bound(ax+1,ax+1+gs1,xx[i])-ax-1;
        yy[i]=lower_bound(by+1,by+1+gs2,yy[i])-by-1;
        aa[i]=lower_bound(ax+1,ax+1+gs1,aa[i])-ax-1;
        bb[i]=lower_bound(by+1,by+1+gs2,bb[i])-by-1;
    }
    R=lower_bound(ax+1,ax+1+gs1,R)-ax-1;
    C=lower_bound(by+1,by+1+gs2,C)-by-1;
    for(i=1;i<=n;++i)
    {
        x=xx[i],y=yy[i],a=aa[i],b=bb[i];
        if(x!=0&&x!=R&&y!=0&&y!=C)continue;
        if(a!=0&&a!=R&&b!=0&&b!=C)continue;
        if(x>a){swap(x,a),swap(y,b);}
        else{if(x==a&&y>b)swap(y,b);}
        B[++tot]=(op){x,y,a,b};
    }sort(B+1,B+1+tot,com);
    for(i=1;i<=tot;++i)
    {
        x=B[i].x;y=B[i].y;a=B[i].a;b=B[i].b;
        bd(x,y,a,b);
        if(a==0)xi.modify(b);
        if(a==R)xa.modify(b);
        if(b==0)yi.modify(a);
        if(b==C)ya.modify(a);
    }puts("YES");
	return 0;
}


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

int main() {
  int x;
  string s = "ai1333";
  cin >> x;
  x/=100;

  for(int i=0; i<x; ++i) {
    s += "3";
  }

  cout << s << endl;

  return 0;
}



Measured memory_bytes: 3204
using System;
using System.Collections.Generic;
using System.Linq;

namespace CSharpSample01
{
    
    class Program
    {
    
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int N = int.Parse(input[0]);
            int M = int.Parse(input[1]);

            int[] state = new int[N + 1];
            long[] case_num = new long[N + 1];
            long max = 1000000007;

            for(int i = 0; i <= N; i++)
            {
                state[i] = 0;
            }

            for(int i = 0; i < M; i++)
            {
                int broken_num = int.Parse(Console.ReadLine());
                state[broken_num] = 1;
            }

            case_num[0] = 1;

            if(state[1] == 0)
            {
                case_num[1] = 1;
            }
            else
            {
                case_num[1] = 0;
            }

            for(int n = 2; n <= N; n++)
            {

                if(case_num[n - 1] == 0 && case_num[n - 2] == 0)
                {
                    Console.WriteLine(0);
                    return;
                }

                if(state[n] == 1)
                {
                    case_num[n] = 0;
                }
                else
                {
                    case_num[n] = case_num[n - 1] + case_num[n - 2];
                }                

                if(case_num[n] > max)
                {
                    case_num[n] %= max;
                }
            }

            Console.WriteLine(case_num[N]);
        
        }
    }
}

Measured memory_bytes: 14048
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define int long long
#define INF 1000000000000000000
using namespace std;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;

#define ANS(f) if(f) cout << "YES" << endl; else cout << "NO" << endl;

template<typename T>
void readv(vector<T> &a){ REP(i, a.size()) cin >> a[i]; }
void readi(vector<int> &a){ REP(i, a.size()){cin >> a[i]; a[i]--;} }



signed main(){

    string s; cin >> s;
    cout << s.substr(0, 4) << " " << s.substr(4, 8) << endl;
    
    return 0;
}

Measured memory_bytes: 256
S = list(input())

dic = {}

for s in S:
    if s not in dic:
        dic[s] = 1
    else:
        dic[s] += 1

ok = True
for k in dic:
    if dic[k] == 2:
        pass
    else:
        ok = False

if ok:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3060
#include<iostream>

using namespace std;

int main() {
	int a, b, c, d, res1, res2;
	cin >> a >> b >> c >> d;

	int i = 0;

	res1 = a;
	res2 = c;

	for (i = 0; ; i++) {
		
		res2 -= b;
		if (res2 <= 0) {
			cout << "Yes";
			break;
		}

		
		res1 -= d;
		if (res1 <= 0) {
			cout << "No";
			break;
		}
		
	}



	return 0;

}

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

vector<vector<int>> g;
vector<int> pt;

int dfs(int p)
{
  if (pt[p] != -1)
    return pt[p];
  if (g[p].size() == 0)
  {
    pt[p] = 0;
    return 0;
  }
  int l = 0;
  for (int i: g[p])
    l = max(l, dfs(i));
  pt[p] = l + 1;
  return pt[p];
}

int main()
{
  int n, m;
  cin >> n >> m;
  g.resize(n);
  pt.resize(n);
  fill(pt.begin(), pt.end(), -1);
  rep(i, m)
  {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    g[x].push_back(y);
  }
  int ans = 0;
  rep(i, n)
    ans = max(ans, dfs(i));
  cout << ans << endl;
  return 0;
}

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

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define hash sodnf9843bsd
#define ll long long
#define INF (1<<29)
#define INFF 0x7fffffff
#define LINF (1ll<<60)
#define LINFF 0x7fffffffffffffff
#define PI 3.14159265359
#define _fi(n) for(int i = 0;i < n;i++)
#define _fj(n) for(int j = 0;j < n;j++)
#define _fk(n) for(int k = 0;k < n;k++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define YESNO(ans) cout << (ans?"YES":"NO") << endl
#define prec(x) cout << fixed << setprecision(x)
#define pqueue priority_queue
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define endl '\n'

int dp[3003][3003] = {};
int rdp[3003][3003] = {};

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

    string s, t;cin>>s>>t;
    int n = (int)s.size();
    int m = (int)t.size();

    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            if (s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1]+1;
            else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
        }
    }

    string ans = "";
    int i = n;
    int j = m;
    while(i > 0 && j > 0){
        while(i > 0 && dp[i][j] == dp[i-1][j]) i--;
        while(j > 0 && dp[i][j] == dp[i][j-1]) j--;
        if (dp[i][j] > 0) ans += s[i-1];
        j--;
        i--;
    }

    reverse(all(ans));
    cout << ans << endl;

    return 0;
}


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

using namespace std;

int64_t solve(int N, int cost, vector<tuple<size_t, size_t, int64_t>>& edges) {
  constexpr auto NONE = numeric_limits<int64_t>::min();
  vector<int64_t> dp(N + 1, NONE);
  dp[1] = 0;
  vector<int64_t> prev;
  auto value1 = NONE;
  for (int i = 0; i < N; ++i) {
    prev.clear();
    fill_n(back_inserter(prev), N + 1, NONE);
    prev.swap(dp);
    for (auto&& edge : edges) {
      auto from = get<0>(edge);
      if (prev[from] != NONE) {
        auto to = get<1>(edge);
        auto coins = get<2>(edge);
        dp[to] = max(dp[to], prev[from] - cost + coins);
      }
    }
    value1 = max(value1, dp[N]);
  }
  if (value1 == NONE) {
    return -1;
  }
  auto value2 = NONE;
  for (int i = 0; i < N; ++i) {
    prev.clear();
    fill_n(back_inserter(prev), N + 1, NONE);
    prev.swap(dp);
    for (auto&& edge : edges) {
      auto from = get<0>(edge);
      if (prev[from] != NONE) {
        auto to = get<1>(edge);
        auto coins = get<2>(edge);
        dp[to] = max(dp[to], prev[from] - cost + coins);
      }
    }
    value2 = max(value2, dp[N]);
  }
  if (value1 < value2) {
    return -1;
  }
  return value1 <= 0 ? 0 : value1;
}

int main() {
  int N, M, cost;
  cin >> N >> M >> cost;
  vector<tuple<size_t, size_t, int64_t>> edges;
  for (int i = 0; i < M; ++i) {
    int from, to, coins;
    cin >> from >> to >> coins;
    edges.emplace_back(from, to, coins);
  }
  cout << solve(N, cost, edges) << endl;
}


Measured memory_bytes: 640
import scala.util.control.Breaks._

object Main extends App {
  val Array(n, m) = scala.io.StdIn.readLine().split(' ').map(_.toInt)
  val as = Array.fill(n)(scala.io.StdIn.readLine().toCharArray)
  val bs = Array.fill(m)(scala.io.StdIn.readLine.toCharArray)

  breakable {
    for (hi <- 0 to n - m) {
      for (w <- 0 to n - m) {
        val tmp = (for (h <- 0 until m) yield {
          as(h + hi).slice(w, w + m)
        }).toArray

        if (tmp.corresponds(bs) { _ sameElements _ }) {
          println("Yes")
          break()
        }
      }
    }

    println("No")
  }
}


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

int main(){
    
    string S;
    cin>>S;
    int N=S.size();
    vector<int> A(26,0);
    for(int i=0;i<N;i++){
        A[S[i]-'a']++;
    }
    if(N<26){
        for(int i=0;i<26;i++){
            if(A[i]==0){
                char X='a'+i;
                S=S+X;
                break;
            }
        }
        cout<<S<<endl;
    }
    else{
        if(S=="zyxwvutsrqponmlkjihgfedcba") cout<<-1<<endl;
        else{
            for(int j=24;j>=0;j--){
                bool flag=true;
            char Y=S[j],Z='z';
            for(int i=j+1;i<26;i++){
                if(S[i]>Y&&S[i]<=Z){
                    flag=false;
                    Z=S[i];
                }
            }
                if(!flag){
                    cout<<S.substr(0,j)+Z<<endl;
                    break;
        }
    }
}
}
}


Measured memory_bytes: 256
ab=[list(map(int,input().split(" "))) for _ in range(3)]
d=[]
for i in ab:
    d.append(i[0])
    d.append(i[1])
if d.count(1)>=3 or d.count(2)>=3 or d.count(3)>=3 or d.count(4)>=3:
    print("NO")
else:
    print("YES")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, n1, n2, n3, n4;
  cin >> n;
  n1 = n / 1000;
  n2 = n % 1000 / 100;
  n3 = n % 100 / 10;
  n4 = n % 10;
  if ( ((n1 == n2) && (n2 == n3)) || ((n2 == n3) && (n3 == n4)) ) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
n, m = map(int, input().split())
x = [0] * m
y = [0] * m
z = [0] * n
ac = 0
wa = 0
for i in range(m):
    x[i], y[i] = map(str, input().split())
    if z[int(x[i]) - 1] >= 0:
        if y[i] == 'AC':
            ac += 1
            wa += z[int(x[i]) - 1]
            z[int(x[i]) - 1] = -1
        else:
            z[int(x[i]) - 1] += 1
print(ac, wa)


Measured memory_bytes: 16460
extern crate core;

use std::fmt;
use std::cmp::{Ordering, min, max};
use std::fmt::{Display, Error, Formatter, Binary};
use std::f32::MAX;
use std::ops::{Add, Sub, Mul, Div, Neg, Index, IndexMut};
use std::collections::{BTreeMap, VecDeque, BinaryHeap, BTreeSet};

fn show<T: Display>(vec: &Vec<T>) {
    if vec.is_empty() {
        println!("[]");
    }else {
        print!("[{}", vec[0]);
        for i in 1 .. vec.len() {
            print!(", {}", vec[i]);
        }
        println!("]");
    }
}
fn show2<T: Display>(vec: &Vec<Vec<T>>) {
    if vec.is_empty() {
        println!("[]");
    }else {
        for l in vec {
            show(l);
        }
    }
}
macro_rules! read_line{
    () => {{
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).ok();
        line
    }};
    (delimiter: ' ') => {
        read_line!().split_whitespace().map(|x|x.to_string()).collect::<Vec<_>>()
    };
    (delimiter: $p:expr) => {
        read_line!().split($p).map(|x|x.to_string()).collect::<Vec<_>>()
    };
    (' ') => {
        read_line!(delimiter: ' ')
    };
    ($delimiter:expr) => {
        read_line!(delimiter: $delimiter)
    };
    (' '; $ty:ty) => {
        read_line!().split_whitespace().map(|x|x.parse::<$ty>().ok().unwrap()).collect::<Vec<$ty>>()
    };
    ($delimiter:expr; $ty:ty) => {
        read_line!($delimiter).into_iter().map(|x|x.parse::<$ty>().ok().unwrap()).collect::<Vec<$ty>>()
    };
}
macro_rules! read_value{
    () => {
        read_line!().trim().parse().ok().unwrap()
    }
}
macro_rules! let_all {
    ($($n:ident:$t:ty),*) => {
        let line = read_line!(delimiter: ' ');
        let mut iter = line.iter();
        $(let $n:$t = iter.next().unwrap().parse().ok().unwrap();)*
    };
}
macro_rules! let_mut_all {
    ($($n:ident:$t:ty),*) => {
        let line = read_line!(delimiter: ' ');
        let mut iter = line.iter();
        $(let mut $n:$t = iter.next().unwrap().parse().ok().unwrap();)*
    };
}
fn primes(upper_limit: usize) -> Vec<i32> {
    let mut is_prime = vec![true; upper_limit + 1];
    let mut i = 4;
    while i <= upper_limit {
        is_prime[i] = false;
        i += 2;
    }
    i = 3;
    while i <= upper_limit {
        if is_prime[i] {
            let mut j = i * i;
            while j <= upper_limit {
                is_prime[j] = false;
                j += i;
            }
        }
        i += 2;
    }
    let mut result = Vec::new();
    for i in 2 .. is_prime.len() {
        if is_prime[i] {
            result.push(i as i32);
        }
    }
    result
}
fn main() {
    let mut prime = primes(10000);
    for i in 1 .. prime.len() {
        prime[i] += prime[i - 1];
    }
    loop {
        let_all!(n: i32);
        if n == 0 {
            return
        }
        let mut count = 0;
        for &to in &prime {
            if (to > n && prime.binary_search(&(to - n)).is_ok()) || (n == to) {
                count += 1
            }
        }
        println!("{}", count);
    }
}


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

typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
#define f first
#define s second
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0)

string s,t;
int main(){
	cin>>s>>t;
	int ans = 0;
	FOR(i,0,s.size() - 1){
		if (s[i] != t[i]) ans++;
	}
	cout<<ans;
}


Measured memory_bytes: 3848