akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <queue>
using namespace std;

typedef pair<int, int> Point;
int h, w, n;
string grid[1001];

int bfs(int sx, int sy, int gx, int gy){
    bool visited[1001][1001] = {false};
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};

    visited[sy][sx] = true;

    queue<pair<Point, int> > que;
    pair<Point, int> state;
    que.push(make_pair(Point(sx, sy), 0));
    while (1){
        state = que.front();
        que.pop();

        if (state.first.first == gx && state.first.second == gy){
            return state.second;
        }

        for (int i = 0; i < 4; i++){
            int nx = state.first.first + dx[i];
            int ny = state.first.second + dy[i];
            if (0 <= nx && nx < w && 0 <= ny && ny < h 
                && grid[ny][nx] != 'X' && visited[ny][nx] == false){
                visited[ny][nx] = true;
                que.push(make_pair(Point(nx, ny), state.second + 1));
            }
        }
    }
}

int main(int argc, char const *argv[]){
    int sx, sy, gx, gy;
    int ans = 0;
    cin>>h>>w>>n;
    for (int i = 0; i < h; i++){
        cin>>grid[i];
    }

    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++){
            if (grid[i][j] == 'S'){
                sx = j; sy = i;
            }
            if (grid[i][j] == '1'){
                gx = j; gy = i;
            }
        }
    }

    for (int size = 2; size-1 <= n; size++){
        ans += bfs(sx, sy, gx, gy);

        sx = gx; sy = gy;
        for (int i = 0; i < h; i++){
            for (int j = 0; j < w; j++){
                if (grid[i][j] - '0' == size){
                    gx = j; gy = i;
                }
            }
        }
    }

    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 4964
// Created by Nandu Vinodan
#include <bits/stdc++.h>

#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define rep(i,a,n) for(int i=a;i<=(n);++i)
#define repD(i,a,n) for(int i=a;i>=(n);--i)
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define vi vector<int>
#define pi pair<int, int>
#define INF INT_MAX
#define _INF INT_MIN
#define TC 0 

using namespace std;
using ll = long long;

void testcase() {
    int n, k;
    cin >> n >> k;

    vector<ll> v(n);
    rep(i, 0, n-1) cin >> v[i];

    sort(v.begin(), v.end(), greater<ll>());

    int ct = 0, i = 0;
    while (i < n && ct < k) {
    	i++;
    	ct++;
    }

    ll res = 0;
    while (i < n) {
    	res += v[i];
    	i++;
    }
    cout << res << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    if (TC)
        cin>>t;
    while(t--) {
        testcase();
    }
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main(){
    string s;cin >> s;
    if(s=="ABC")cout << "ARC" <<endl;
    else cout << "ABC" <<endl;
}

Measured memory_bytes: 3520
#include<bits/stdc++.h>
typedef long long ll;
//#define mod 1000000007

using namespace std;

bool cal(ll a, ll b) {
    cout<<a<<" "<<b<<endl;
	if (a << 1 > b) 
		return 1; 
	b >>= 1; 
	if (a << 1 > b) 
		return (b - a) & 1; 
	if (b & 1) 
		return (b - a) & 1; 
	return cal(a, b >> 1); 
}
  bool mo(const ll &a,const ll  &b){
      return abs(a)>abs(b);
  }
  ll mod=1e9+7;
  ll cal(ll A[], int n, int k) 
{ 
    sort(A, A + n); 
  
    // variable to store final product of all element 
    // of sub-sequence of size k 
    ll product = 1; 
  
    // CASE I 
    // If max element is 0 and 
    // k is odd then max product will be 0 
    if (A[n - 1] == 0 && (k & 1)) 
        return 0; 
  
    // CASE II 
    // If all elements are negative and 
    // k is odd then max product will be 
    // product of rightmost-subarray of size k 
    if (A[n - 1] <= 0 && (k & 1)) { 
        for (int i = n - 1; i >= n - k; i--) {
            product *= A[i]%mod; 
            product%=mod;
        }
        return product%mod; 
    } 
  
    // else 
    // i is current left pointer index 
    int i = 0; 
  
    // j is current right pointer index 
    int j = n - 1; 
  
    // CASE III 
    // if k is odd and rightmost element in 
    // sorted array is positive then it 
    // must come in subsequence 
    // Multiplying A[j] with product and 
    // correspondingly changing j 
    if (k & 1) { 
        product *= A[j]%mod;
        product%=mod;
        j--; 
        k--; 
    } 
  
    // CASE IV 
    // Now k is even 
    // Now we deal with pairs 
    // Each time a pair is multiplied to product 
    // ie.. two elements are added to subsequence each time 
    // Effectively k becomes half 
    // Hence, k >>= 1 means k /= 2 
    k >>= 1; 
  
    // Now finding k corresponding pairs 
    // to get maximum possible value of product 
    for (int itr = 0; itr < k; itr++) { 
  
        // product from left pointers 
        ll left_product = (A[i] * A[i + 1]); 
  
        // product from right pointers 
        ll right_product = (A[j] * A[j - 1]); 
  
        // Taking the max product from two choices 
        // Correspondingly changing the pointer's position 
        if (left_product > right_product) { 
            product *= (left_product%mod);
            product%=mod;
            i += 2; 
        } 
        else { 
            product *= right_product%mod;
            product%=mod;
            j -= 2; 
        } 
    } 
  
    // Finally return product 
    return product%mod; 
}
 //vector<int>vis(200005,0);
main() {
    int n;
    cin>>n;
    vector<pair<int,int>> adj;
      ll res = 0;
     
      for (ll i = 1; i <= n; ++i) {
        res += i * (n-(i-1));
      }
      for (ll i = 0; i < n-1; ++i) {
        ll x, y;
        cin >> x >> y;
        x--; y--;
        adj.push_back({x, y});
        ll minv = min(x, y);
        ll maxv = max(x, y);
        res -= (minv+1) * (n-maxv);
      }
      cout << res << endl;
}

Measured memory_bytes: 5312
import java.util.Scanner;

class Main
{
	public static void main(String args[])
	{
		Scanner sc = new Scanner(System.in);
		while (true)
		{
			int n = sc.nextInt();
			int m = sc.nextInt();
			if (n == 0 && m == 0) break;
			int bord[] = new int[n];
			for (int i = 0; i < n; i++)
			{
				bord[i] = sc.nextInt();
			}
			int move[] = new int[m];
			for (int i = 0; i < m; i++)
			{
				move[i] = sc.nextInt();
			}
			int pos = 0;
			int i;
			for (i = 0; i < m; i++)
			{
				pos += move[i];
				if (pos + 1 >= n) break;
				pos += bord[pos];
				if (pos + 1 >= n) break;
			}
			System.out.println(i+1);
		}
	}
}

Measured memory_bytes: 12000
n, w = map(int, input().split())
weight = []
value = []
INF = 10 ** 9
#dp[x][y] = x-1番目までの品物から価値がyを達成するように
#           選んだときの重さの最小値
ans = 0

for i in range(n):
    x, y = map(int, input().split())
    weight.append(x)
    value.append(y)

dp = [[ INF for i in range(sum(value) + 1)] for j in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    for j in range(sum(value) + 1):
        if j - value[i] >= 0:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - value[i]] + weight[i])

        else:
            dp[i + 1][j] = dp[i][j]


for i in sorted(range(sum(value) + 1), reverse = True):
        tmp = dp[n][i]
        if tmp <= w:
            print(i)
            exit()


Measured memory_bytes: 168752
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        String[] lines = getStdin();
        String number = lines[0];
        String[] line = number.split(" ");
        int T_hp = Integer.parseInt(line[0]);
        int T_attack = Integer.parseInt(line[1]);
        int A_hp = Integer.parseInt(line[2]);
        int A_attack = Integer.parseInt(line[3]);

        for (int i = 0; i < 100; i++){
            A_hp = A_hp - T_attack;
            if (A_hp <= 0){
                System.out.println("Yes");
                return;
            }
            T_hp = T_hp - A_attack;
            if (T_hp <= 0){
                System.out.println("No");
                return;
            }
        }


    }
  
  private static String[] getStdin() {
    Scanner scanner = new Scanner(System.in);
    ArrayList<String> lines = new ArrayList<>();
    while (scanner.hasNext()) {
      lines.add(scanner.nextLine());
    }
    return lines.toArray(new String[lines.size()]);
  }
  
}


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

#define watch(x) cerr << (#x) << ": " << (x) << endl
#define int long long

const int N = 100009;
int h, n, a[N];

int32_t main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    int tot = 0;
    for(int i = 0; i < n; ++i) {
        tot += a[i];
    }

    if(tot >= h) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
    
    return 0;
}


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

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	string S; cin >> S;
  int N = S.size();
  int P = 2019;
	long long ans = 0;
	if (P == 2 || P == 5) {
		for (int i = 0; i < N; i++) {
			int v = S[i] - '0';
			if (v % P == 0) {
				ans += i+1;
			}
		}
	} else {
		reverse(S.begin(), S.end());
		unordered_map<int, int> mp;
		mp[0] ++;
		int pref = 0;
		int pref10 = 1;
		for (char c  : S) {
			int v = c - '0';

			pref += v * pref10;
			pref %= P;

			ans += mp[pref]++;

			pref10 *= 10;
			pref10 %= P;
		}
	}
	cout << ans << '\n';

	return 0;
}


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

int main(){
	string s;
	cin>>s;
	int sum=700;
	for(int i=0;i<3;i++){
		if(s[i]=='o'){
			sum += 100;
		}
	}	
	cout<<sum;
	return 0;
}


Measured memory_bytes: 256
# include <iostream>
# include <set>
#include <algorithm>
#include <math.h>
# include<map>
typedef long long ll;
using namespace std;

ll rem(ll num, ll a) {
    while (num >= a) {
        num -= a;
    }
    return num;
}

int main() {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    int ans = c-(a-b);
    if (ans > 0)
        cout << ans << endl;
    else
        cout << 0 << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
from io import StringIO
import unittest

base=["a","b","c","d","e","f","g","h","i","j"]

def yn(b):
    print("Yes" if b==1 else "No")
    return

def loopx(used,ans,anslen,nn):
    for x in range(0,used+2):
        ans2 = ans + base[x]
        anslen2=anslen+1
        if x==(used+1):
            used+=1
        if anslen>=nn:
            print(ans2)
        else:
            loopx(used,ans2,anslen2,nn)



inn=int(input())

loopx(-1,"",0,inn-1)

sys.exit()


Measured memory_bytes: 6988
// 基本テンプレート
 
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
using namespace std;
 
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

set<int> S;
int N, Q;
bool used[100010];
int perm[100010], idx[100010];

void ins_elem() {
    int x = idx[1];
    int l = perm[x-1], r = perm[x+1];
    if(1 <= l && l <= N) S.insert(l);
    if(1 <= r && r <= N) S.insert(r);
}

signed main() {
    cin >> N >> Q;
    repq(i,1,N) {
        perm[i] = idx[i] = i;
    }

    rep(i,0,Q) {
        ins_elem();
        int A, B; cin >> A >> B;
        swap(idx[perm[A]], idx[perm[B]]);
        swap(perm[A], perm[B]);
        ins_elem();
    }
    S.insert(1);

    cout << S.size() << endl;
    return 0;
}

Measured memory_bytes: 1792
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		Solver solver = new Solver();
		solver.init();
		solver.readHead(in.readLine());
		// for (; solver.hasNext();) {
		// solver.readBody(in.readLine());
		// }
	}
}

class Solver {
	int N;
	int cnt;

	public void init() {
		N = 0;
		cnt = 0;
	}

	public void readHead(String str) {
		String[] strArr = str.split(" ");
		// N = Integer.parseInt(strArr[0]);
		// System.out.println(N);
		if (strArr[0].charAt(strArr[0].length() - 1) != strArr[1].charAt(0)) {
			System.out.println("NO");
			return;
		}
		if (strArr[1].charAt(strArr[1].length() - 1) != strArr[2].charAt(0)) {
			System.out.println("NO");
			return;
		}
		System.out.println("YES");

	}

	public boolean hasNext() {
		return cnt < N;
	}

	public void readBody(String str) {
		// System.out.println(str);
		cnt++;
	}
}


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

int main(){
  int A, B;
  cin >> A >> B;
  string str;
  cin >> str;
  if(str.size()!=A+B+1){
    cout << "No"<<endl;
    return 0;
  }
  for(int i=0; i<str.size(); i++){
    if(i==A){
      if(str[i]!='-'){
        cout << "No"  <<endl;
        return 0;
      }
    }
    else if(!(str[i]>='0' && str[i]<='9')){
      cout << "No" <<endl;
      return 0;
    }
  }
  cout << "Yes" <<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  string table[]={"",".,!? ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
  char str[1280];
  int a;
  cin>>a;
  for(int i=0;i<a;i++){
    cin>>str;
    int r=0;
    char now='0';
    for(int i=0;str[i];i++){
            if(now!=str[i]){
                if(now!='0'){
		  cout<<table[now-'0'][(r-1)%table[now-'0'].size()];
                }
                r=1;
                now=str[i];
            }else r++;
    }
	    cout<<endl;
  }
  return 0;
}



Measured memory_bytes: 3016
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
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; }
using ll = long long;
using vi = vector<int>; using vvi = vector<vi>;
const ll MOD = 1e9+7; ll INF = 1LL << 60;
const vi d8x = {1, 0, -1, 0, 1, -1, -1, 1}; vi d8y = {0, 1, 0, -1, 1, 1, -1, -1};
const vi d4x = {1, 0, -1, 0}; vi d4y = {0, 1, 0, -1};
//---------------------------------------

int main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    int cnt=1;
    for(int i=0; i<n-1; i++){
        if(s[i]!=s[i+1]){
            cnt++;
        }
    }
    cout<<cnt<<endl;
}

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

typedef long long int ll;

int N;
vector<int> X1, X2, Y1, Y2;

vector<ll> compress(vector<ll> xs){
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    return xs;
}

int main(){
    cin >> N;
    
    vector<ll> xs, ys;
    for(int i=0; i<N; i++){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        
        X1.push_back(x1);
        Y1.push_back(y1);
        X2.push_back(x2);
        Y2.push_back(y2);
        
        xs.push_back(x1); xs.push_back(x2);
        ys.push_back(y1); ys.push_back(y2);
    }
    
    xs = compress(xs);
    ys = compress(ys);
    
    int X = xs.size();
    int Y = ys.size();
    
    vector<vector<bool>> field(X, vector<bool>(Y, false));
    
    for(int i=0; i<N; i++){
        int x1i = lower_bound(xs.begin(), xs.end(), X1[i]) - xs.begin();
        int x2i = lower_bound(xs.begin(), xs.end(), X2[i]) - xs.begin();
        int y1i = lower_bound(ys.begin(), ys.end(), Y1[i]) - ys.begin();
        int y2i = lower_bound(ys.begin(), ys.end(), Y2[i]) - ys.begin();
        
        for(int x=x1i; x<x2i; x++)
            for(int y=y1i; y<y2i; y++)
                field[x][y] = true;
    }
    
    ll ans = 0;
    for(int x=0; x<X-1; x++){
        for(int y=0; y<Y-1; y++) if(field[x][y]){
            ans += (xs[x+1]-xs[x])*(ys[y+1]-ys[y]);
        }
    }
    cout << ans << endl;
    
    return 0;
}

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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////
#define MOD (ll)(1e9+7)
ll N,Q;
vector<pair<ll,pll>> abv[101010];
ll d[101010];
ll P[101010][40];
ll e[101010][2];
vector<pair<ll,pll>> Cdb[101010];
ll len[202020];
ll Fa[101010];
ll i,j,k,ans;

void Init(ll a,ll p,ll& q){
    P[a][0] = p;
    
    d[a] = d[p] + 1;
    ll i = 0;
    fornum(i,0,abv[a].size()){
        if(abv[a][i].first==p)
            continue;
        ll bb = abv[a][i].second.first;
        e[abv[a][i].first][0] = ++q;
        Cdb[bb].push_back({q,
         {Cdb[bb][Cdb[bb].size() - 1].second.first + 1,
         Cdb[bb][Cdb[bb].size() - 1].second.second + abv[a][i].second.second}});
        //printf("%lld:%lld %lld %lld\n", bb,q, Cdb[bb][Cdb[bb].size() - 1].second.first, Cdb[bb][Cdb[bb].size() - 1].second.second);
        len[q] = len[q - 1] + abv[a][i].second.second;
        Init(abv[a][i].first, a,q);
        e[abv[a][i].first][1] = ++q;
        Cdb[bb].push_back({q,
         {Cdb[bb][Cdb[bb].size() - 1].second.first - 1,
         Cdb[bb][Cdb[bb].size() - 1].second.second - abv[a][i].second.second}});
        len[q] = len[q - 1] - abv[a][i].second.second;
    }
}
ll par(ll a,ll n){
    ll i = 0;
    while(n){
        if(n&1)
            a = P[a][i];
        i++;
        n >>= 1;
    }
    return a;
}
ll cpar(ll a,ll b){
    if(d[a]<d[b])
        b=par(b, d[b] - d[a]);
    else
        a=par(a, d[a] - d[b]);
    if(a==b)
        return a;
    for (ll i = 29; i >= 0;i--){
        ll pa = par(a, 1 << i);
        ll pb = par(b, 1 << i);
        if(pa!=pb){
            a = pa;
            b = pb;
        }
    }
    return P[a][0];
}
ll clen(ll a,ll x,ll y){
    ll l = 0, r = Cdb[x].size() - 1;
    while(l<r){
        ll c = (l + r+1) / 2;
        if (Cdb[x][c].first<=e[a][0]){
            l = c;
        }else{
            r = c - 1;
        }
    }
    //printf("%lld,%lld,%llda\n", x, a, l);
    return len[e[a][0]] + Cdb[x][l].second.first * y - Cdb[x][l].second.second;
}
ll solve(ll x,ll y,ll u,ll v){
    return clen(u, x, y) + clen(v, x, y) - 2 * clen(cpar(u, v), x, y);
}


int main(){
    scanf("%lld%lld", &N,&Q);
    fornum(i,1,N){
        ll a, b,c,d;
        scanf("%lld%lld%lld%lld", &a,&b,&c,&d);
        abv[a].push_back({b,{c,d}});
        abv[b].push_back({a,{c,d}});
    }
    fornum(i,0,101010){
        Cdb[i].push_back({0, {0, 0}});
    }
    Init(1, 0, i = 0);
    //fornum(i,0,N){
    //    printf("%lld:%lldb\n", e[i + 1][0], e[i + 1][1]);
    //}
    fornum(i,1,30){
        fornum(j,0,N){
            P[j+1][i] = P[P[j+1][i - 1]][i - 1];
        }
    }
    while(Q--){
        ll x, y, u, v;
        scanf("%lld%lld%lld%lld", &x, &y, &u, &v);
        //printf("%lld ", cpar(u, v));
        printf("%lld\n", solve(x, y, u, v));
    }
    


    return 0;
}

Measured memory_bytes: 67248
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<random>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(long long i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) {rep(_,v.size())cout<<" "<<v[_];cout<<endl;}
#define show2d(v) {rep(__,v.size())show1d(v[__]);}
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int> tp;
typedef vector<tp> vt;
typedef vector<vt>vvt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
#define yes cout<<"Yes\n"
#define no cout<<"No\n"

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

	int n,m;
	cin>>n>>m;
	vvi G(n);
	rep(i,m){
		int a,b;
		cin>>a>>b;
		a--;b--;
		G[a].pb(b);
		G[b].pb(a);
	}
	vi out(n,-1);
	queue<int>q;
	q.push(0);
	out[0]=0;
	while(!q.empty()){
		int a=q.front();
		q.pop();
		rep(i,G[a].size()){
			int to=G[a][i];
			if(out[to]+1)continue;
			out[to]=a;
			q.push(to);
		}
	}
	yes;
	rep(i,n-1)cout<<out[i+1]+1<<endl;
}


Measured memory_bytes: 12976
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())
#define fi first
#define se second

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<endl;
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;
const ll inf=1e15;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n,x;
  cin>>n>>x;
  vector<ll> a(2*n);
  vector<vector<ll>> b(n,vector<ll>(n,inf));
  rep(i,n){
    cin>>a[i];
    a[i+n]=a[i];
  }
  FOR(i,n,2*n){
    b[i-n][0]=a[i];
    FOR(k,1,n){
      b[i-n][k]=min(b[i-n][k-1],a[i-k]);
    }
  }
  ll ans=inf;
  rep(k,n){//魔法を唱える回数をk回に固定
    ll cnt=k*x;
    rep(i,n){
      cnt+=b[i][k];
    }
    ans=min(ans,cnt);
  }
  cout<<ans<<endl;
}

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

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

    while (true) {
        c = c - b;
        if (c <= 0) break;
        a = a - d;
        if (a <= 0) break;
    }
    if (a > 0 && c <= 0) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

Measured memory_bytes: 3568
#include <stdio.h>

int main(){
  int n;
  scanf("%d",&n);
  int i;
  int p[10]={};
  for (i=0;i<n;i++)
    scanf("%d",&p[i]);
  int max=0;
  int sum=0;
  for (i=0;i<n;i++){
    if (p[i]>max)
      max=p[i];
    sum+=p[i];
  }
  printf("%d\n",sum-max/2);
  return 0;
}

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

int a[1919810];

void P(int u,int v) {
	cout<<u<<' '<<v<<'\n';
}

int main() {
	int n,x=1;cin>>n;
	while(x<n) x<<=1;
	if(n==x) return puts("No"),0;
	x>>=1;
	puts("Yes");
	if(n%4==3) {
		for(int i=1;i<2*n;i++) P(i,i+1);
	}
	else if(n%4==1) {
		for(int i=2;i<n;i++) P(i,i+1),P(i+n,i+n+1);
		P(1,2);P(n,n+2);P(n+1,n+3);
	}
	else if(n%4==0) {
		for(int i=1;i<n;i++) a[i]=i;
		swap(a[x-1],a[n^x]);
		for(int i=1;i<=n-2;i++) P(a[i],a[i+1]),P(n+a[i],n+a[i+1]);
		P(a[n-1],n+a[1]);P(n,x);P(2*n,n^x);
	}
	else {
		for(int i=2;i<n;i++) a[i]=i;
		swap(a[x-1],a[n^x]);
		if((n^x)==2&&n!=6) swap(a[x-2],a[3]);
		for(int i=2;i<=n-2;i++) P(a[i],a[i+1]),P(n+a[i],n+a[i+1]);
		P(a[n-1],n+a[2]);P(n,x);P(2*n,n^x);P(1,2);P(n+1,3);
	}
	return 0;
}


Measured memory_bytes: 3200
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
int a,b,c,d;
int main()
{
	fast;
	cin>>a>>b>>c>>d;
	if (abs(a-b)<=d && abs(b-c)<=d || abs(a-c)<=d)
	   cout<<"Yes"<<endl;
	else
	   cout<<"No"<<endl; 
	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i=(a); i<(int)(b); i++)
#define FORD(i, a, b) for (int i=a; i>(int)(b); i--)
#define PPC(x) __builtin_popcount(x)
#define SZ(x) ((int)(x).size())
#define MSB(x) (31 - __builtin_clz(x))
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define ithBit(m, i) ((m) >> (i) & 1)
#define ft first
#define sd second
#ifdef DEBUG
#include "debug.h"
#else
#define dbg(...) 0
#endif
using namespace std;
 
const int maxN = 3006, mod = 998244353;

int T[maxN];
long long dp[maxN][maxN], dp2[maxN][maxN];

void solve()
{
	int n, s;
	scanf ("%d%d", &n, &s);
	FOR(i, 1, n+1)
		scanf ("%d", T+i);
	dp[0][0] = 1ll;
	FOR(i, 1, n+1)
	{
		dp[i][0] = i+1;
		FOR(j, 1, s+1)
		{
			if (T[i] <= j)	
				dp2[i][j] = dp[i-1][j-T[i]];
			dp[i][j] = (dp[i-1][j] + dp2[i][j]) % mod;
		}
	}	
	long long res = 0;
	FOR(i, 1, n+1)
	{
		dp2[i][s] *= (n+1-i);
		res = (res + dp2[i][s]) % mod;
	}
	printf("%lld\n", res);
}
 
int main()
{
	int t;
	t=1;//scanf ("%d", &t);
	while (t--)
		solve();
	return 0;
}


Measured memory_bytes: 141312
#include<stdio.h>
int main(void)
{
	int a,b;
	char op;
	while(1){
	scanf("%d %c %d",&a,&op,&b);
	
	if(op==42){
		printf("%d\n",a*b);
	}else if(op==43){
		printf("%d\n",a+b);
	}else if(op==45){
		printf("%d\n",a-b);
	}else if(op==47){
		printf("%d\n",a/b);
	}else if(op==63){
		exit(0);
	}
	}
	return 0;
}

Measured memory_bytes: 600
import numpy as np
n, k = map(int, input().split())
p = np.array(list(map(int, input().split())))
p += 1
sum_E = np.cumsum(p)
sum_e = np.append([0], sum_E)
ans = -1
for i in range(n-k+1):
    ans = max(ans, sum_e[i+k] - sum_e[i])
print(ans/2)

Measured memory_bytes: 33972
/*
 *  Author :: Kattu37
 */

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

#define ll long long
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define sortallr(x) sort(allr(x))
#define PI 3.1415926535897932384626
#define mod 1000000007

typedef pair<int, int>  pii;
typedef pair<ll, ll>  pll;
typedef vector<int>   vi;
typedef vector<ll>    vl;
typedef vector<pii>   vpii;
typedef vector<pll>   vpl;
typedef vector<vi>    vvi;
typedef vector<vl>    vvl;

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

	int c1 = 0, c2 = 0, c3 = 0, c4 = 0;

	string str;
	for (int i = 0; i < n; i++)
	{
		cin >> str;
		if (str == "AC")
			c1++;
		else if (str == "WA")
			c2++;
		else if (str == "TLE")
			c3++;
		else c4++;
	}

	cout << "AC x " << c1 << "\n";
	cout << "WA x " << c2 << "\n";
	cout << "TLE x " << c3 << "\n";
	cout << "RE x " << c4 << "\n";
}

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

	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}

	return 0;
}


Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
#define fs first
#define sc second

const int nmax = 100;
int t = 1;
int n, s1, s2;

void INPUT()
{
     cin >> n;
     int x;
     for(int i = 1; i <= n; i++) {
          cin >> x;
          s1 += x;
          s2 += x * x;
     }
}

void INIT()
{

}

void SOLVE()
{
     cout << (s1 * s1 - s2) / 2;
}

int main()
{
    //freopen("test.inp","r",stdin);
    INPUT();
    INIT();
    while (t--) SOLVE();
    return 0;
}



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

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

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

  vector<ll> a(n);
  vector<ll> b(n);
  rep(i,n) cin >> a.at(i) >> b.at(i);

  ll ans=0;
  rep(i,n){
    int j = n-1-i;
    int r = (a.at(j)+ans)%b.at(j);
    if(r!=0) ans += b.at(j)-r;
  }

  cout << ans;
}

Measured memory_bytes: 4844
#include<bits/stdc++.h>
#define EPS (1e-15)
using namespace std;

int K,R,L;
double P,E,T,ans,cnt;

void func(int k,double l,double r,double p){
  double h=(l+r)/2;
  cnt++;
  if(l-(T+E)>EPS||T-E-r>EPS)return;
  else if(l-(T-E)>=EPS&&T+E-r>=EPS){
    ans+=p;
    return;
  }
  if(k==K){
    if(E-abs(h-T)>=EPS)ans+=p;
    return;
  }
  if(T<=h){
    func(k+1,l,h,p*(1-P));
    func(k+1,h,r,p*P);
  }else{
    func(k+1,l,h,p*P);
    func(k+1,h,r,p*(1-P));
  }
}

int main(){
  cin>>K>>R>>L>>P>>E>>T;
  func(0,R,L,1);
  //cout<<cnt<<endl;
  printf("%.15f\n",ans);
  return 0;
}

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

using lint = long long;

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

    string s;
    cin >> s;
    lint n = s.size();
    lint ans = n * (n - 1) / 2 + 1;
    map<int, int> num;
    for (int i = 0; i < n; i++) {
        ans -= num[s[i] - 'a'];
        num[s[i] - 'a']++;
    }

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

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

int main(){
    string a;
    cin >> a;
    //int count =700;
    a[0] = '2'; 
    a[1] = '0';
    a[2] = '1';
    a[3] = '8';
    cout << a << endl;
    
}

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

// statics
using namespace std;
using int64 = int_fast64_t;
using PAIR = pair<int64, int64>;
constexpr int INF = 1 << 30;
constexpr int64 LINF = 1LL << 60;
constexpr int MOD = 1e9 + 7;
constexpr int MAX_N = 3e5 + 1;

// init/input
#define int int64
#define INIT ios::sync_with_stdio(false);cin.tie(0);
#define VAR(type, ...) type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__);
template<typename T> void MACRO_VAR_Scan(T &t) {cin>>t;}
template<typename First, typename...Rest> void MACRO_VAR_Scan(First &first, Rest&...rest) {cin>>first;MACRO_VAR_Scan(rest...);}
#define VEC(type, c, n) vector<type> c(n);for(auto &&i:c)cin>>i;

// out
#define OUT(dist) cout<<(dist);
#define FOUT(n, dist) cout<<fixed<<setprecision(n)<<(dist);
#define SP cout<<" ";
#define BR cout<<endl;
#define zero(n) cout<<setfill('0')<<right<<setw(n)
#define debug(x) cerr<<#x<<":"<< (x);BR;

// utility
#define ALL(a) (a).begin(), (a).end()
#define EACH(i, a) for(auto &&i:(a))
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RFOR(i, a, b) for(int i=(b)-1;i>=0;--i)
#define REP(i, n) for(int i=0;i<(n);++i)
#define RREP(i, n) for(int i=(n)-1;i>=0;--i)

signed main() {
  INIT;
	VAR(int, n);
	VEC(int, a, n);

	// 1縺壹ｌ
	vector< int > sm(n + 1, 0);
	REP(i, n) {
		sm[i+1] = sm[i] + a[i];
		// debug(sm[i+1]);
	}

	sort(ALL(sm));
	int tmp = 1, ans = 0;

	REP(i, n) {
		// debug(sm[i]);
		if (sm[i] != sm[i+1]) {
			ans += tmp * (tmp - 1) / 2;
			tmp = 0;
		}
		++tmp;
	}

	if (tmp > 0) ans += tmp * (tmp - 1) / 2;
	OUT(ans)BR;
	
  
  return 0;
}


Measured memory_bytes: 3456
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int main(){
	int n;	cin>>n;
	vector<long long> a(n);
	for(int i=0;i<n;i++)	cin>>a[i];
	sort(a.begin(),a.end());
	int ret=1;
	long long sum=a[0];
	for(int i=1;i<n;i++){
		if(2*sum>=a[i])	ret++;
		else 	ret=1;
		sum+=a[i];
	}
	cout<<ret<<endl;
	return 0;
}


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

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

    if(ss.at(0)==ss.at(1)&&ss.at(2)==ss.at(3)&&ss.at(0)!=ss.at(2)) cout << "Yes" << endl;
    else if(ss.at(0)==ss.at(2)&&ss.at(1)==ss.at(3)&&ss.at(0)!=ss.at(1)) cout << "Yes" << endl;
    else if(ss.at(0)==ss.at(3)&&ss.at(1)==ss.at(2)&&ss.at(0)!=ss.at(1)) cout << "Yes" << endl;
    else cout << "No" << endl;

    return (0);
}


Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const long double EPS=1e-9;
const long double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
long double ABS(long double a){return max(a,-a);}
char in[5];
int main(){
	scanf("%s",in);
	int ret=0;
	for(int i=0;i<4;i++){
		if(in[i]=='+')ret++;
		else ret--;
	}printf("%d\n",ret);
}


Measured memory_bytes: 128
#include<iostream>
#include<stdlib.h>
using namespace std;

int main(){
	int N,i;
	cin>>N;
	if(N<=9){
		cout<<"Yes";
		return 0;
	}else if(N>81){
		cout<<"No";
		return 0;
	}
	for(i=2;i<=9;i++){
		if(N%i==0){
			if(N/i<=9){
				cout<<"Yes";
				return 0;
			}
		}
	}
	if(i==10){
		cout<<"No";
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <numeric>
#include <math.h>
#include <algorithm>
#include <float.h>
#include <limits>
#include <vector> 
#include <string.h>
#include <iomanip>

#define rep(i,a,n) for(ll int (i) = (a);(i) < (n);(i)++)
#define urep(i,a,n) for(ll int (i) = (a);(i) > (n);(i)--)
#define MOD 1000000007
#define Imax 2147483647
#define ll long long
#define asort(a) sort(a.begin(),a.end());

using namespace::std;

int jo(ll int jxo, ll int jyo){//累乗
	ll int jhogeo = 1;
	rep(jinto,0,jyo) jhogeo=jhogeo*jxo;
	return jhogeo;
}
char tobig(char toxbig){//char大文字化
  return (toxbig-0x20);
}
char tolow(char toxlow){//char小文字化
  return (toxlow+0x20);
}
int ctoi(char cctoi){//char->int
  if('0' <= cctoi && cctoi <= '9') return (cctoi-'0');
  return -1;
}
int gcd(int gcad, int gcbd) {//最大公約数
  if(gcad < gcbd) return gcd(gcbd, gcad);
  int gcrd;
  while ((gcrd=gcad%gcbd)) {
    gcad = gcbd;
    gcbd = gcrd;
  }
  return gcbd;
}
int lcm(int lcam, int lcbm){//最小公倍数
 return (lcam*lcbm)/gcd(lcam,lcbm);
}


int main(){
  int N,M;
  cin>>N>>M;
  vector<vector<int>> s(M, vector<int>(N));
  vector<int> k(M);
  vector<int> p(M);
  rep(i,0,M){
    cin>>k[i];
    rep(j,0,k[i]) cin>>s[i][j];
  }
  int count=0;
  int check=0;
  int num=0;
  rep(i,0,M) cin>>p[i];
  rep(ramp,0,jo(2,N)){
    
    rep(i,0,M){
      rep(j,0,k[i]){
        num=num+!!(ramp&jo(2,s[i][j]-1));
     //   cout<<ramp<<" "<<jo(2,s[i][j]-1)<<" "<<(ramp&jo(2,s[i][j]-1))<<"/";
      }
      //cout<<num<<" "<<p[i]<<" "<<ramp<<endl;
      if((num%2)==(!p[i])){
       // cout<<"b";
        check++;
        num=0;
        break;
      }
      num=0;
    }
    if(!check){
      count++;
     // cout<<"a";
    }
    check=0;
  }
  cout<<count;
        
      
      
  
  
}
// int *p = new int[N];

//  vector<int> 変数名(要素数);
//  sort(変数名.begin(),変数名.end());//昇順ソート

// vector<vector<int>> 変数名(左の個数, vector<int>(右の個数));

//


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
const int INF = 10010001;

int main() {
	int x, y, a, b, c;
	cin >> x >> y >> a >> b >> c;
	pair<long long, int> apple[300009];
	for (int i = 0; i < a; ++i) {
		cin >> apple[i].first;
		apple[i].second = 1;
	}
	for (int i = 0; i < b; ++i) {
		cin >> apple[a+i].first;
		apple[a+i].second = 2;
	}
	for (int i = 0; i < c; ++i) {
		cin >> apple[a+b+i].first;
		apple[a+b+i].second = 0;
	}
	sort(apple, apple + a + b + c, greater < pair<long long, int>>());
    //for(int i=0;i<a+b+c;++i) cout<<apple[i].first<<" "<<apple[i].second<<endl;
	
    long long ans = 0;
	bool endx = false, endy = false;
	vector<int> count(4,0);
	for (int i = 0; i < a + b + c; ++i) {
		if (apple[i].second == 1 && endx) continue;
		if (apple[i].second == 2 && endy) continue;
		ans += apple[i].first;
		count[apple[i].second]++;
		count[3]++;
		if (count[1] == x) endx = true;
		if (count[2] == y) endy = true;
		if (count[3] == x + y) break;
	}
	cout << ans << endl;
}



Measured memory_bytes: 4992
mod = 10 ** 9 + 7
n, k = map(int, input().split())

fact = [1] * (2 * n + 1)
inv = [1] * (2 * n + 1)
invf = [1] * (2 * n + 1)
for i in range(2, 2 * n + 1):
  fact[i] = fact[i-1] * i % mod
  inv[i] = -inv[mod % i] * (mod // i) % mod
  invf[i] = invf[i-1] * inv[i] % mod

count = 0
for i in range(min(n, k+1)):
  c = fact[n] * invf[n-i] * invf[i] % mod
  count += c * fact[n-1] * invf[n-i-1] * invf[i] % mod
  count %= mod
print(count)

Measured memory_bytes: 50420
/*
    Author:zeke

    pass System Test!
    GET AC!!
*/
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
    ll(s);      \
    cin >> (s);
#define Scin(s) \
    ll(s);      \
    cin >> (s);
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;
}
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll mod = 1e9 + 7;
ll MOD = 1e9 + 7;
ll INF = 1e18;
// cout << "Case #" << index << " :IMPOSSIBLE";
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    string s;
    cin>>s;
    rep(i,s.size()){
        if(s[i]=='?'){
            s[i]='D';
        }
    }
    cout<<s<<endl;
}


Measured memory_bytes: 3740
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

typedef struct {
    int x, y;
} POINT;

POINT p[100000];
POINT add[100000], minus[100000];
int group[2][100000];
int n;

int comp(const void *a, const void *b)
{
    POINT p, q;
    
    p = *(POINT *)a;
    q = *(POINT *)b;
    
    return (p.x - q.x);
}

int canDivide(int piv)
{
    int i;
    int a, b;
    
    for (i = 0; i < n; i++){
        group[0][i] = group[1][i] = 2;
    }
    group[0][add[0].y] = 0;
    //suppose distance will be given by |c[0][i] - c[0][j]|
    
    for (i = 0; i < n; i++){
        if (abs(add[i].x - add[0].x) > piv && abs(add[i].x - add[n - 1].x) > piv){
            return (0);
        }
        if (abs(add[i].x - add[0].x) > piv){
            group[0][add[i].y] = 1;
        }
        if (abs(add[i].x - add[n - 1].x) > piv){
            group[0][add[i].y] = 0;
        }
    }
    
    //suppose distance will be given by |c[1][i] - c[1][j]|
    
    group[1][minus[0].y] = 0;
    for (i = 0; i < n; i++){
        if (abs(minus[i].x - minus[0].x) > piv && abs(minus[i].x - minus[n - 1].x) > piv){
            return (0);
        }
        if (abs(minus[i].x - minus[0].x) > piv){
            group[1][minus[i].y] = 1;
        }
        if (abs(minus[i].x - minus[n - 1].x) > piv){
            group[1][minus[i].y] = 0;
        }
    }
    
    a = b = 0;
    for (i = 0; i < n; i++){
        if (group[0][i] == 2 || group[1][i] == 2){
            b++;
            continue;
        }
        if (group[0][i] != group[1][i]){
            a++;
        }
    }
    
    return (a == 0 || a + b == n);
}

int main(void)
{
    int i;
    int left, right, center;
    
    scanf("%d", &n);
    
    for (i = 0; i < n; i++){
        scanf("%d%d", &p[i].x, &p[i].y);
        add[i].x = p[i].x + p[i].y;
        minus[i].x = p[i].x - p[i].y;
        add[i].y = minus[i].y = i;
    }
    
    qsort(add, n, sizeof(POINT), comp);
    qsort(minus, n, sizeof(POINT), comp);
    
    left = 0;
    right = 400000;
    
    while (left != right){
        center = (left + right) / 2;
        if (canDivide(center)){
            right = center;
        }
        else {
            left = center + 1;
        }
    }
    
    printf("%d\n", right);
    
    return (0);
}

Measured memory_bytes: 3588
#include <iostream>
#include <vector>

using namespace std;

#define ll long long

struct edge {
  int to;
  ll cost;
};

vector<edge> tree[100010];
ll cost_k[100010];

void dfs(int v, int par, ll dist) {
  cost_k[v] = dist;

  for (int i = 0; i < (int)tree[v].size(); i++) {
    if (tree[v][i].to == par)continue;
    dfs(tree[v][i].to, v, dist + tree[v][i].cost);
  }
}

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

  for (int i = 0; i < N - 1; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    tree[a].push_back({ b, c });
    tree[b].push_back({ a, c });
  }
  int Q, K;
  cin >> Q >> K;
  K--;

  dfs(K, -1, 0);

  for (int i = 0; i < Q; i++) {
    int x, y;
    cin >> x >> y;
    x--; y--;
    cout << cost_k[x] + cost_k[y] << endl;
  }
}


Measured memory_bytes: 15912
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<iterator>
#include<complex>
#include<stack>
#include "stdio.h"
using namespace std;

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

using ll = long long;
using Pii = pair<int, int>;

const int inf = 1e9 + 7;
const ll longinf = 1LL << 50;
const long long mod_const = 1e9 + 7;

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

using MIte = multimap<ll, ll, greater<ll> >::iterator;

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; }

using pll = pair<long long, long long>;

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

	ll X,Y;
	cin >> X >> Y;

	ll ans = 0;
	if (X == 1) {
		ans += 300000;
	}
	else if (X == 2) {
		ans += 200000;
	}
	else if (X == 3) {
		ans += 100000;
	}

	if (Y == 1) {
		ans += 300000;
	}
	else if (Y == 2) {
		ans += 200000;
	}
	else if (Y == 3) {
		ans += 100000;
	}

	if (X == 1 && Y == 1) {
		ans += 400000;
	}

	cout <<  ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main (){

	int H,W;

	

	while(1){
		cin >> H >> W;
		if(H == 0 && W == 0)break;
	
for ( int i = 0; i < H; i++ ){
    for ( int j = 0; j < W; j++ ){
        cout << "#";
    }
    cout << endl;
}
cout << endl;
}

return 0;
}

Measured memory_bytes: 1152
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int multiple = Integer.parseInt(br.readLine());
		String input = br.readLine();
		String[] inputArray = input.split(" ");
		
		int start = Integer.parseInt(inputArray[0]);
		int end = Integer.parseInt(inputArray[1]);
		
		for (int i = start; i <= end; i++) {
			if (i % multiple == 0) {
				System.out.println("OK");
				System.exit(0);
			}
		}
		System.out.println("NG");
		System.exit(0);
	}
}

Measured memory_bytes: 25544
def cul(li,s):
  a = 0
  for i in li:
    a += (i - s)**2
  
  return a

N = int(input())
li = list(map(int,input().split()))

s1 = sum(li)//len(li)
s2 = s1 + 1

ans1 = cul(li,s1)
ans2 = cul(li,s2)

print(min(ans1,ans2))


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

#define int long long
//typedef pair<int, int> P;
#define mod 1000000007
#define INF (1LL<<60)
 
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
#define YES puts("YES")
#define Yes puts("Yes")
#define NO  puts("NO")
#define No  puts("No")
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
 
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
 
 
#if 1
//-------------
// DUMPマクロ
// https://www.creativ.xyz/dump-cpp-652/
 
// vector
template <typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    for (T& x : vec) is >> x;
    return is;
}
// pair
template <typename T, typename U>
ostream& operator<<(ostream& os, pair<T, U>& pair_var) {
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}
// vector
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    os << "{";
    for (int i = 0; i < vec.size(); i++) {
        os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
    }
    os << "}";
    return os;
}
// map
template <typename T, typename U>
ostream& operator<<(ostream& os, map<T, U>& map_var) {
    os << "{";
    repi(itr, map_var) {
        os << *itr;
        itr++;
        if (itr != map_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
// set
template <typename T>
ostream& operator<<(ostream& os, set<T>& set_var) {
    os << "{";
    repi(itr, set_var) {
        os << *itr;
        itr++;
        if (itr != set_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
 
#define DUMPOUT cerr
 
void dump_func() {
    DUMPOUT << endl;
}
template <class Head, class... Tail>
void dump_func(Head&& head, Tail&& ... tail) {
    DUMPOUT << head;
    if (sizeof...(Tail) > 0) {
        DUMPOUT << ", ";
    }
    dump_func(std::move(tail)...);
}
#ifdef DEBUG
#define DEB
#define dump(...)                                                              \
    DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                            \
            << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]"        \
            << endl                                                            \
            << "    ",                                                         \
        dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define dump(...)
#endif
#endif



signed main() {
    int N;
    cin >> N;
    vector<int> a(N);
    rep(i,N) cin >> a[i];

    vector<int> dp(N+1, 0);

    for(int i=0; i<N; i++){
        dp[a[i]] = dp[a[i]-1]+1;
    }
    int ma = -INF;
    rep(i,N+1) ma = max(ma, dp[i]);
    cout << N - ma << endl;
}



Measured memory_bytes: 3328