akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <map>
#include <algorithm>
#include <functional>
#include <string>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>
using namespace std;

#define REP(i,p,n) for(ll i=p;i<ll(n);++i)
#define rep(i,n) REP(i,0,n)

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

ll R, C, K;

const ll MAXN = 3001;
ll S[MAXN][MAXN];
ll dp[MAXN][MAXN][4];

int main()
{
    cin >> R >> C >> K;

    rep (i, K)
    {
        ll x, y;
        cin >> y >> x; --x; --y;
        cin >> S[x][y];
    }

    ll ans = 0;

    const auto update = [&ans](auto* dst, auto src)
    {
        *dst = max(*dst, src);
        ans = max(ans, *dst);
    };

    for (ll y=0;y<R;++y)
    for (ll x=0;x<C;++x)
    {
        // 取らないで隣に移動する
        rep (k, 4) { update(&dp[x + 1][y][k], dp[x][y][k]); }

        // 取って隣に移動する
        rep (k, 3) { update(&dp[x + 1][y][k + 1], dp[x][y][k] + S[x][y]); }

        // 取らないで次の行へ
        rep (k, 4) { update(&dp[x][y + 1][0], dp[x][y][k]); }

        // 取って次の行へ
        rep (k, 3) { update(&dp[x][y + 1][0], dp[x][y][k] + S[x][y]); }
    }

    cout << ans << endl;

    return 0;
}


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

int main() {
	int n; cin >> n;
	long double JPY=0; long double BTC=0;
	rep(i,n) {
		long double x; string u; cin >> x >> u;
		if(u=="BTC") BTC+=x;
		else JPY+=x;
	}
	long double ans=JPY+BTC*380000;
	cout << ans << endl;
}

Measured memory_bytes: 3808
//
//  main.cpp
//

#include <algorithm>
#include <array>
#include <assert.h>
#include <complex>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <math.h>
#include <memory>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = int64_t;
using ull = uint64_t;
constexpr ll LL_MAX = numeric_limits<ll>::max();
constexpr ull ULL_MAX = numeric_limits<ull>::max();

template<typename T>
vector<T> make_vec_nd(T init, ll size) {
	return vector<T>(size, init);
}
template<typename T, typename... Args>
auto make_vec_nd(T init, ll size, Args... rest) {
	auto inner = make_vec_nd(init, rest...);
	return vector<decltype(inner)>(size, inner);
}

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrep(i, a, b) for (ll i = (a)-1; i >= (b); i--)

ll N;

int main() {
    cin >> N;
    unordered_map<ll, unordered_map<ll, ll>> cnt;
    rep(n,1,N+1) {
        ll num = n;
        vector<ll> digits;
        while (num > 0) {
            digits.push_back(num % 10);
            num /= 10;
        }
        cnt[digits.back()][digits.front()]++;
    }
    ll ans = 0;
    rep(i,1,10) {
        rep(j,0,10) {
            ans += cnt[i][j] * cnt[j][i];
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1144
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ff first
#define ss second
#define sf scanf
#define pf printf
#define MAX 200002
#define INF 100000000000000
#define EXP 1e-6
#define endl '\n'
#define all(v) v.begin(), v.end()
#define FOR(i, a, b, c) for( int i = a; i < b; i+=c )
#define rep(i, a) for( int i = 0; i < a; i++ )
#define fastio ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);

typedef long long ll;
const int maxn = 1e5 + 10;
const ll MOD = 1e9 + 7;

using namespace std;

typedef pair <int, int> ii;
typedef pair <int, ii> trie;
typedef vector <int> vi;
typedef vector <ii> vii;
typedef vector <vii> vvii;
typedef vector <vi> vvi;
typedef vector <bool> vb;
typedef vector <trie> vtrie;
typedef bitset <maxn> bs;

int n, val[120];
ll wgt[120];
ll dp[120][maxn];

ll knapsack( int pos, int value ) {

	ll &ret = dp[pos][value];
	if( value == 0 ) return 0LL;
	if( pos >= n || value < 0 ) return INF;
	if( ret != -1 ) return ret;

	ll nilam = 0LL, nilam_na = 0LL;
	nilam_na = knapsack( pos + 1, value );
	nilam = wgt[pos] + knapsack( pos + 1, value - val[pos] );

	return ret = min( nilam, nilam_na );
}


int main()
{
	fastio

    ll w;
    cin >> n >> w;
    for( int i = 0; i < n; i++ )
    	cin >> wgt[i] >> val[i];

    memset( dp, -1, sizeof(dp) );
    for( int i = n*1000; i >= 0; i-- ) {
    	ll ans = knapsack( 0, i );
    	if( ans <= w ) {
    		cout << i << endl;
    		return 0;
    	}
    }

	return 0;

}

Measured memory_bytes: 94080
#include <bits/stdc++.h>
using namespace std;
const int maxn = 123456;
int a[maxn], p[maxn], v[maxn];
int main(){
  int n, k; cin >> n >> k;
  cout << (n - 1 + k - 2) / (k - 1) << endl;
  return 0;
}
 



Measured memory_bytes: 256
s = input()
s_return = s[::-1]
x = (len(s) - 1)// 2
s_1_x = s[:x]
s_1_x_return = s_1_x[::-1]
y = (len(s) + 3)//2
s_1_y = s[y - 1:len(s)]
s_1_y_return = s_1_y[::-1]

if s == s_return:
    if s_1_x == s_1_x_return and s_1_y == s_1_y_return:
        print("Yes")
    else:
        print("No")
else:
    print("No")

Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct UnionFind
{
	vector<int> par;
	vector<int> con;
	UnionFind(int N) : par(N),con(N)
	{
		for(int i=0;i<N;i++)
		{
			par[i]=i;
			con[i]=1;
		}
	}
	int root(int x)
	{
		if (par[x]==x) return x;
		return par[x]=root(par[x]);
	}
	void unite(int x,int y)
	{
		int rx=root(x);
		int ry=root(y);
		if(rx==ry)return;
		par[rx]=ry;
		con[ry]+=con[rx];
	}
	bool same(int x,int y)
	{
		int rx=root(x);
		int ry=root(y);
		return rx==ry;
	}
};

long long c2(long long a)
{
	return a*(a-1)/2;
}


int main()
{
	long long n,m;
	cin >> n >> m;
	
	UnionFind tree(n);

	vector<long long> ans;
	vector<int> a,b;

	for(int i=0;i<m;i++)
	{
		int aa,bb;
		cin >> aa >> bb;
		a.push_back(aa-1);
		b.push_back(bb-1);
	}
	reverse(a.begin(),a.end());
	reverse(b.begin(),b.end());
	
	long long conb=0;

	for(int i=0;i<m;i++)
	{
		ans.push_back(c2(n)-conb);
		long long tmp=tree.con[tree.root(b[i])];
		long long tmp2=tree.con[tree.root(a[i])];
		tree.unite(a[i],b[i]);
		if(tree.con[tree.root(b[i])]!=tmp)
		{
			conb+=c2(tree.con[tree.root(b[i])]);
			conb-=(c2(tmp)+c2(tmp2));
		}
	}

	reverse(ans.begin(),ans.end());

	for(int i=0;i<ans.size();i++)
		cout << ans[i] << endl;
}


Measured memory_bytes: 3824
#include <iostream>
#include <cmath>

int main()
{
  int N;
  std::cin>>N;
  
  int result=0;
  for(int i=1;i<=N;i++)
  {
    if(static_cast<int>(std::log10(i)+1)%2==1)
    {
      result++;
    }
  }
  
  std::cout<<result<<std::endl;
  
  return 0;
}

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

int main() {
    long long X, Y;
    cin >> X >> Y;
    long long ans = 0;
    for (long long i = X; i <= Y;) {
        ans++;
        i *= 2;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())
using namespace std;

using ll = long long;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const int INF = 1e9;
const long long INFLL = 1LL<<60;

const ll mod = 1e9+7;

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

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

  ll ans = k;
  rep(i, n-1) {
    ans *= k;
    ans %= mod;
  }

  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = (int)1e9 + 7;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T, class T2> void smin(T& a, T2 val) {if (a > val) a = val;}template<class T, class T2> void smax(T& a, T2 val) {if (a < val) a = val;}
const int N = 5*(int)1e5 + 10;

double PI = acosl(-1);
int a, b, h, m;

vector<double> getPoints(double thetha, int x){
   vector<double> ans;

   double X, Y;
   X = x * cosl(thetha);     
   Y = x * sinl(thetha);
   // if (thetha <= 90){
   //    thetha = 90 - thetha;
   //    X = x * cosl(thetha);     
   //    Y = x * sinl(thetha);
   // }
   // else if (thetha <= 180){
   //    thetha -= 90;
   //    X = x * cosl(thetha);     
   //    Y = -x * sinl(thetha);
   // }
   // else if (thetha <= 270){
   //    thetha = 270 - thetha;
   //    X = -x * cosl(thetha);     
   //    Y = -x * sinl(thetha);
   // }
   // else{
   //    thetha = thetha - 270;
   //    X = -x * cosl(thetha);     
   //    Y = x * sinl(thetha);
   // }

   ans.push_back(X);
   ans.push_back(Y);
   return ans;
}

void solve(){
   cin >> a >> b >> h >> m;

   double thetha = ((h + (m / 60.0)) / 12.0) * 2 * PI;
   double delta = (m / 60.0) * 2 * PI;

   double x = a*cosl(thetha) - b*cosl(delta);
   double y = a*sinl(thetha) - b*sinl(delta);

   // auto hr = getPoints(thetha, a);
   // auto min = getPoints(delta, b);

   cout << fixed << setprecision(15);
   cout << hypotl(x, y);
}

int32_t main(){_
   
   int t = 1;
   //cin >> t;

   while(t--){
     solve();
     cout << endl;
   }
   

   return 0;
}

Measured memory_bytes: 4152
from queue import Queue
K = int(input())
q = Queue()
for i in range(1,10):
    q.put(i)

def generator(n):
    end = n % 10
    for i in range(-1,2):
        i += end
        if 0 <= i <= 9:
            yield l*10+i

ans = list(range(1,10))

while len(ans) < K:
    l = q.get()
    for i in generator(l):
        q.put(i)
        ans.append(i)

print(ans[K-1])


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

int main(void){
    long long int i, j, k, n, a, b, ans=0, po=0;
    char name[30];
    scanf("%s", name);
    printf("%c%c%c", name[0], name[1], name[2]);
    
}

Measured memory_bytes: 1676
import sys
sys.setrecursionlimit(10 ** 7)


def longdist(p, dp_l, out_l):
    if len(out_l[p]) == 0:
        return 0
    for q in out_l[p]:
        if dp_l[q] == -1:
            dp_l[q] = longdist(q, dp_l, out_l)
        dp_l[p] = max(dp_l[p], dp_l[q]+1)
    return dp_l[p]


n, m = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(m)]

input, output = [[] for _ in range(n)], [[] for _ in range(n)]
for x, y in xy:
    input[y - 1].append(x - 1)
    output[x - 1].append(y - 1)

dp = [-1] * n
for i in range(n):
    if dp[i] == -1:
        dp[i] = longdist(i, dp, output)

print(max(dp))


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

using namespace std;

int n, m, x;

bool ok(vector<int> a, int x){
    for(int i = 0; i < m; i++){
        if(a[i] < x){
            return false;
        }
    }
    return true;
}

int main(void){
    cin >> n >> m >> x;
    vector<int> c(n);
    vector<vector<int> > a(n, vector<int>(m));
    for(int i = 0; i < n; i++){
        cin >> c[i];
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }
    int minj = 10000000;
    //i番目の本を
    for(int bit = 0; bit < (1 << n); bit++){
        vector<int> ans(m);
        int sum = 0;
        for(int i = 0; i < n; i++){
            if(bit & (1 << i)){
                sum += c[i];
                for(int j = 0; j < m; j++){
                    ans[j] += a[i][j];
                }
            }
        }
        bool frag = true;
        for(int i = 0; i < m; i++){
            if(ans[i] < x)frag = false;
        }
        if(frag){
            minj = min(minj, sum);
        }
    }
    if(minj == 10000000){
        minj = -1;
    }
    cout << minj << endl;
}

Measured memory_bytes: 3632
#include<algorithm>
#include<climits>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<utility>
#include<vector>

#define lint long long
#define VI vector<int>
#define VL vector<lint>
#define VC vector<char>
#define VVI vector<vector<int>>
#define rep(i, n) for(int i = 0 ; i < n ; i++)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c.begin(), c.end(), greater<int>())
#define IINF INT_MAX
#define LLINF LLONG_MAX

using namespace std;

int main(){
    double n, m, d;
    cin >> n >> m >> d;
    if(d == 0){
        cout << fixed << setprecision(8) << (m - 1) / n << endl;
    }else{
        cout << fixed << setprecision(8) << 2 * (n - d) * (m - 1) / (n * n) << endl;
    }
    return 0;
}

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

int main() {
    while (true) {
        int n, m, a;
        cin >> n >> m >> a;
        if ((n | m | a) == 0) {
            break;
        }
        int* verticalLinesHeight = new int [m];
        pair<int, int>* verticalLines = new pair<int, int> [m];
        for (int i = 0; i < m; i++) {
            int h, p, q;
            cin >> h >> p >> q;
            verticalLinesHeight[i] = h;
            verticalLines[i].first = p;
            verticalLines[i].second = q;
        }
        for (int i = 0; i < m - 1; i++) {
            for (int j = 0; j < m - 1 - i; j++) {
                if (verticalLinesHeight[j] < verticalLinesHeight[j + 1]
                    || (verticalLinesHeight[j] == verticalLinesHeight[j + 1] && verticalLines[j].first < verticalLines[j + 1].first)) {
                    int tempH = verticalLinesHeight[j];
                    verticalLinesHeight[j] = verticalLinesHeight[j + 1];
                    verticalLinesHeight[j + 1] = tempH;
                    int tempFirst = verticalLines[j].first, tempSecond = verticalLines[j].second;
                    verticalLines[j].first = verticalLines[j + 1].first;
                    verticalLines[j].second = verticalLines[j + 1].second;
                    verticalLines[j + 1].first = tempFirst;
                    verticalLines[j + 1].second = tempSecond;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            if (a == verticalLines[i].first) {
                a = verticalLines[i].second;
            } else if (a == verticalLines[i].second) {
                a = verticalLines[i].first;
            }
        }
        cout << a << endl;
        delete[] verticalLinesHeight;
        delete[] verticalLines;
    }
}

Measured memory_bytes: 912
#include<iostream>
#include<vector>
#include<algorithm>
#include <string>
using namespace std;
int main(void){
    int a;
    cin>>a;
    string b;
    cin>>b;
    if(a<3200){
        cout<<"red"<<endl;
    }else{
        cout<<b<<endl;
    }


    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
int acs(const void *a, const void *b){return *(int*)a - *(int*)b;} /* 1,2,3,4.. */
int des(const void *a, const void *b){return *(int*)b - *(int*)a;} /* 8,7,6,5.. */
#define min(a,b) (a < b ? a: b)
#define max(a,b) (a > b ? a: b)

#define MAXN (100000)
#define MOD (998244353)

int main(void)
{
    char s[10];
    scanf("%s",s);

    if(strcmp(s,"Sunny")==0)
    {
        printf("Cloudy\n");
    }else if(strcmp(s,"Cloudy")==0)
    {
        printf("Rainy\n");
    }else
    {
        printf("Sunny\n");
    }

    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = 0; i <= (n); i++)
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const ll INF = 1LL<<60;
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 Graph = vector<vector<int>>;

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

    cout << (N-K+1) << endl;
}

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

using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define fore(i,a) for(auto &i:a)

typedef pair <int, int> P;
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
const int  INF = 2147483647;
const ll INFL = 9223372036854775807;
const ll mod = 1000000007;


int main() {
	int n;
	cin >> n;
	VI h(n);
	REP(i, n)cin >> h[i];
	VI dp(100010, 0);
	dp[0] = 0;
	dp[1] = abs(h[1] - h[0]);
	FOR(i, 2, n) {
		dp[i] = min(dp[i - 2] + abs(h[i] - h[i - 2]), dp[i - 1] + abs(h[i] - h[i - 1]));
	}
	cout << dp[n-1] << endl;

	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <utility>
#include <string.h>
#include <map>
#include <stack>
#include <iomanip>
#include <chrono>
#include <random>
#include <math.h>
#include <time.h>
#include <bitset>
#include <assert.h>
#define rnd mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) x.begin(),x.end()
#define PII pair <ll,ll>
#define N 100007
#define MOD 1000000007
#define INF 1000000000000000000
using namespace std;

vector <int> V[N];
int dp[N];

void dfs(int x) {
    if(dp[x] >= 0) return;
    dp[x] = 0;
    for(auto g: V[x]) {
        dfs(g);
        dp[x] = max(dp[x], 1 + dp[g]);
    }
}

int main() {
    int n, m, x, y;
    cin >> n >> m;
    for(int i = 0; i <= n; i++) {
        dp[i] = -1;
    }
    for(int i = 0; i < m; i++) {
        cin >> x >> y;
        V[x].pb(y);
    }
    for(int i = 1; i <= n; i++) {
        dfs(i);
    }
    x = -1;
    for(int i = 1; i <= n; i++) {
        x = max(x, dp[i]);
    }
    cout << x;
    return 0;
}

Measured memory_bytes: 8192
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <utility>
#include <vector>
 
using namespace std;
 
int main() {
    long long n, ans = 1;
    cin >> n;
    vector<long long> a(n);
    for(long long i = 0; i < n; i++) {
        cin >> a[i];
    }
 
    for(auto v : a) {
        if(v == 0) {
            cout << 0 << endl;
            return 0;
        }
    }
 
    for(long long i = 0; i < n; i++) {
        if(ans > 1000000000000000000 / a[i]) {
            cout << -1 << endl;
            return 0;
        }
        ans = a[i] * ans;
    }
 
    cout << ans << endl;
 
    return 0;
}

Measured memory_bytes: 4060
def main():
    n, *h = map(int, open(0).read().split())

    prev_h = h[-1]
    for cur_h in h[::-1][1:]:
        diff_h = cur_h - prev_h
        if diff_h > 1:
            print('No')
            return()
        prev_h = cur_h
        if diff_h == 1:
            prev_h -= 1

    print('Yes')
    return()

if __name__ == '__main__':
    main()


Measured memory_bytes: 14108
import java.util.*;

public class Main {
    public static void main(String args[]) {

        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt();
        int d = sc.nextInt();
        int x = sc.nextInt();

        int ans = r * x - d;

        for (int i = 0; i < 10; i++){
            System.out.println(ans);
            ans = r * ans - d;
        }
    }
}





Measured memory_bytes: 23892
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

alias W = Tuple!(int, "a", int, "b");

void main()
{
    auto N = readln.chomp.to!int;
    W[] ws;
    foreach (_; 0..N) {
        auto ab = readln.split.to!(int[]);
        ws ~= W(ab[0], ab[1]);
    }
    sort!"a.b > b.b"(ws);
    int last = int.max;
    foreach (w; ws) {
        last = min(last, w.b) - w.a;
    }
    writeln(last >= 0 ? "Yes" : "No");
}

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

int v[105];


int main()
{
    int n;
    cin >> n;
    int sum = 0;
    for(int i = 1;i <= n; ++i){
        cin >> v[i];
        sum += v[i];
    }
    int m;
    cin >> m;
    for(int i = 0, a, b; i < m; ++i){
        cin >> a >> b;
        cout << sum - v[a] + b << '\n';
    }
}


Measured memory_bytes: 256
solve :: [(Int, Int, Int)] -> (Int, Int) -> (Int, Int) -> Int
solve [] (ox, oy) (dx, dy) = w * h
  where w = max 0 $ dx - ox
        h = max 0 $ dy - oy
solve ((x, y, a):xs) (ox, oy) (dx, dy)
  | a == 1 = solve xs (max x ox, oy) (dx, dy)
  | a == 2 = solve xs (ox, oy) (min x dx, dy)
  | a == 3 = solve xs (ox, max y oy) (dx, dy)
  | a == 4 = solve xs (ox, oy) (dx, min y dy)

main :: IO ()
main = do
  [w, h, n] <- map read . words <$> getLine
  let toTuple [x, y, a] = (x, y, a)
  xyas <- map (toTuple . map read . words) . lines <$> getContents
  print $ solve xyas (0, 0) (w, h)

Measured memory_bytes: 1020
#include<stdio.h>
int main(void) {
	int S, hh, h, m, s;
	scanf("%d", &S);
	h = S / 3600;
	hh = S % 3600;
	m = hh / 60;
	s = hh % 60;
	printf("%d:%d:%d\n", h, m, s);
	return 0;
}

Measured memory_bytes: 2740
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		
		String s [] = new String [A];
		for (int i=0; i<A; i++){
			s[i]=sc.next();
		}
		
		boolean ans = true;
		for (int i=0; i<A-1; i++){
			String S = s[i];
			String N = s[i+1];
			int length = S.length();
			//System.out.println(S);
			
			if (S.charAt((length-1))!=N.charAt(0)){
				ans=false;
				break;
			}
		}
		Arrays.sort(s);
		for (int i=0; i<A-1; i++){
			if (s[i].equals(s[i+1])){
				ans=false;
				break;
			}
		}
		
		
		if (ans==false)
			System.out.println("No");
		else
			System.out.println("Yes");
		sc.close();
		
	}

}

Measured memory_bytes: 23764
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
    int d = sc.nextInt();
    String ans;
    if (Math.abs(a - c) <= d) {
      ans = "Yes";
    }else if (Math.abs(a - b) <= d && Math.abs(b - c) <= d) {
      ans = "Yes";
    }else{
      ans = "No";
    }
    System.out.println(ans);
  }

}


Measured memory_bytes: 23764
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using bint = boost::multiprecision::cpp_int;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repSE(i,s,n) for (int i = (s); i < (n); i++)
#define ssort(v) sort(v.begin(), v.end())
#define gsort(v) sort(v.rbegin(), v.rend())
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const deque<T> &vec){ os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename T> bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool chmin(T &m, const T q) { if (q < m) {m = q; return true;} else return false; }

int main()
{
    string S;
    cin >> S;
    cout << (S=="ABC"?"ARC":"ABC") << "\n";
    return 0;
}


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

int main(){
  int n;cin >> n;
  vector<pair<int,int>> a;
  int ord;
  for(int i=0; i<n ;i++){
    cin >>ord; 
    pair<int,int> s = make_pair(ord,i+1);
    a.push_back(s);
  }
  sort(a.begin(), a.end());
  
  for(int i=0; i<n; i++){
    cout << a[i].second;
    if(i==n-1)cout << endl;
    else cout << " ";
  }
  return 0;
}

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

int main(){
    int N;
    int a[200]={0}, count=0;
    cin >> N;
    rep(i, N){
        cin >> a[i];
    }
    while(true){
        rep(i,N){
            if(a[i]%2!=0) goto END;
            else{
                a[i]/=2;
            }
        }
        count++;
    }
END:
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String args[])
	{
		Scanner scan=new Scanner(System.in);
		int n=scan.nextInt();
		int k=scan.nextInt();
		int ar[]=new int[n];
		long sum=0;
		for(int i=0;i<n;i++)
		{
			ar[i]=scan.nextInt();
			sum+=ar[i];
		}
		ArrayList<Integer> div=new ArrayList<Integer>();
		for(int i=1;i*i<=sum;i++)
		{
			if(sum%i==0)
			{
				div.add(i);
				div.add((int)(sum/i));
				
			}
			
		}
		int ans=1;
		for(int x:div)
		{
			int r[]=new int[n];
			for(int i=0;i<n;i++)
			{
				r[i]=ar[i]%x;
			}
			Arrays.sort(r);
			int inc[]=new int[n+1];
			int dec[]=new int[n+1];
			for(int j=0;j<n;j++)
			{
				dec[j+1]=dec[j]+r[j];
				inc[j+1]=inc[j]+(x-r[j]);
				
			}
//			if(x==7) {
//				for(int q:r)System.out.print(q+" ");
//				System.out.println();
////				for(int w:dec)
//				for(int q:dec)System.out.print(q+" ");
//				System.out.println();
//				for(int q:inc)System.out.print(q+" ");
//				System.out.println("new");
//				}
			for(int j=0;j<=n;j++)
			{
				if(dec[j]-dec[0]==inc[n]-inc[j])
				{
					if(dec[j]-dec[0]<=k)
					{
						ans=Math.max(ans,x);
						break;
					}
				}
			}
			
						
			
		}
		System.out.println(ans);
	}
}


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

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n, y;
	cin >> n >> y;
	REP(i, n+1){
		REP(j, n+1-i){
			if (10000*i + 5000*j + 1000*(n-i-j) == y){
				cout << i << " " << j << " " << n-i-j << endl;
				return 0;
			}
		}
	}
	cout << "-1 -1 -1" << endl;
}


Measured memory_bytes: 256
#include <vector>
#include <string>
#include <iostream>
#include <queue>
#include <algorithm>
#include <functional>
#include <map>
#include <array>
#include <cmath>

using namespace std;

int gcd(int a, int b){
    if(a < b){
        return gcd(b, a);
    }

    int r = a % b;
    while(r != 0){
        a = b;
        b = r;
        r = a % b;
    }

    return b;
}

int gcd3(int a, int b, int c){
    int ab = gcd(a, b);
    return gcd(ab, c);
}


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

    long long N;
    cin >> N;

    long long sum = 0;

    for(int a = 1; a <= N; ++a){
        for(int b = 1; b <= N; ++b){
            for(int c = 1; c <= N; ++c){
                sum += gcd3(a, b, c);
            }
        }
    }

    cout << sum;
}


//int main(int argc, char* argv[]){
//    long long N;
//    cin >> N;


//    long long all_sum = (N + 1) * N / 2;

//    long long num_3 = N / 3;
//    long long sum_3 = (num_3 * (6 + (num_3 - 1)*3)) / 2;

//    long long num_5 = N / 5;
//    long long sum_5 = (num_5 * (10 + (num_5 - 1)*5)) / 2;

//    long long num_15 = N/15;
//    long long sum_15= (num_15 * (30 + (num_15 - 1)*15)) / 2;

//    cout << all_sum - sum_3 - sum_5 + sum_15;
//}


Measured memory_bytes: 3636
import sys
input = lambda: sys.stdin.readline().rstrip()
def scc(E):
    n = len(E)
    iE = [[] for _ in range(n)]
    for i, e in enumerate(E):
        for v in e:
            iE[v].append(i)
    T = []
    done = [0] * n # 0 -> 1 -> 2
    ct = 0
    for i0 in range(n):
        if done[i0]: continue
        Q = [~i0, i0]
        while Q:
            i = Q.pop()
            if i < 0:
                if done[~i] == 2: continue
                done[~i] = 2
                T.append(~i)
                ct += 1
                continue
            if i >= 0:
                if done[i]: continue
                done[i] = 1
            for j in E[i]:
                if done[j]: continue
                Q.append(~j)
                Q.append(j)
    
    done = [0] * n
    SCC = []
    for i0 in T[::-1]:
        if done[i0]: continue
        L = []
        Q = [~i0, i0]
        while Q:
            i = Q.pop()
            if i < 0:
                if done[~i] == 2: continue
                done[~i] = 2
                L.append(~i)
                continue
            if i >= 0:
                if done[i]: continue
                done[i] = 1
            for j in iE[i]:
                if done[j]: continue
                Q.append(~j)
                Q.append(j)
        SCC.append(L)
    return SCC

N, M = map(int, input().split())
X = [[] for i in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    X[x].append(y)
S = scc(X)
print(len(S))
for s in S:
    print(*[len(s)] + s)


Measured memory_bytes: 245396
import java.util.Scanner;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.lang.Math;

class Main{

    private final static int DATA_TYPE_INTEGER = 1;
    private final static double DATA_TYPE_DOUBLE = 2.0;
    
    public static void main(String[] args){
        InputStreamReader inputStreamReader = new InputStreamReader(System.in);
        BufferedReader reader = new BufferedReader(inputStreamReader);
        

        // ----- 共通変数 ----- //
        int[] num;
        int DataType = DATA_TYPE_INTEGER;
        //double[] num;
        //double DataType = DATA_TYPE_DOUBLE;
        boolean flag = false; // 提出時はfalse

        // ----- 課題別変数 ----- //
        int Integral;
        
        try {
            while(flag || reader.ready()){
                // データの取得
                num = changeNum(reader.readLine(), DataType);

                Integral = 0;

                // ----- データ処理 ----- //
                for (int i = 1; i < 600/num[0]; i++){
                    Integral += num[0] * num[0] * num[0] * i * i;
                }

                System.out.println(Integral);
                
            }
            reader.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }


    // ----- 自作関数（課題別） ----- //


    // ----- 自作関数（共通） ----- //

    private static int[] changeNum(String str, int DataType){
    //private static double[] getNum(String str){
        String[] data = str.split(" "); 
        int[] num = new int[data.length];

        for (int i = 0; i < data.length; i++){
            num[i] = Integer.parseInt(data[i]);
        }

        return num;
    }

    private static double[] changeNum(String str, double DataType){
        String[] data = str.split(" "); 
        double[] num = new double[data.length];

        for (int i = 0; i < data.length; i++){
            num[i] = Double.parseDouble(data[i]);
        }
            
        return num;
    }

    private static int[] extractList(int[] originalList, int begin, int end){
        int[] list = new int[end - begin];
        int p = 0;

        for (int i = begin; i <= end; i++) {
            list[p++] = originalList[i];
        }

        return list;
    }

    private static double[] extractList(double[] originalList, int begin, int end){
        double[] list = new double[end - begin];
        int p = 0;

        for (int i = begin; i < end; i++) {
            list[p++] = originalList[i];
        }

        return list;
    }

    private static void swap(int[] box, int a, int b) {
        int temp = box[a];
        box[a] = box[b];
        box[b] = temp;
    }

    private static void swap(double[] box, int a, int b) {
        double temp = box[a];
        box[a] = box[b];
        box[b] = temp;
    }
}


Measured memory_bytes: 24108
n,i,j;main(){while(scanf("%d",&n),n){int mi=999;for(i=0;i<110;i++)for(j=0;j<1010;j++)mi=fmin(mi,(n<i*i*i+j*j?999:i+j+n-i*i*i-j*j));printf("%d\n",mi);}return 0;}

Measured memory_bytes: 604
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;
ll MOD = 1e9+7;
//LLONG_MIN

//途中

int main(void){
	ll N,C,x[100010],v[100010],largest=0,cur;
	scanf("%lld%lld",&N,&C);
	reg(i,1,N)scanf("%lld%lld",&x[i],&v[i]);//1-origin
	cur=0;
	ll right[100010]={},right_big[100010]={};
	reg(i,1,N){//時計回り
		cur+=v[i];
		right[i]=cur-x[i];
		right_big[i]=max(right[i],right_big[i-1]);
		largest=max(largest,right[i]);
	}
	cur=0;
	ll left[100010]={},left_big[100010]={};
	ireg(i,1,N){//反時計回り
		cur+=v[i];
		left[i]=cur-(C-x[i]);
		left_big[i]=max(left[i],left_big[i+1]);
		largest=max(largest,left[i]);
	}
	reg(i,1,N){//折り返すやつ
		largest=max(largest,right[i]-x[i]+left_big[i+1]);
		largest=max(largest,left[i]-(C-x[i])+right_big[i-1]);
	}
	printf("%lld\n",largest);
	return 0;
}

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

class Program {
  static void Main() {
    var a = new int[5];
    for (int i = 0; i < 5; i++) {
      var t = int.Parse(Console.ReadLine());
      a[i] = t < 40 ? 40 : t;
    }
    Console.WriteLine(a.Average());
  }
}


Measured memory_bytes: 18300
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;


#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define PSET(x,y) fixed<<setprecision(y)<<x
#define pb push_back
#define pii pair<int,int>
#define pf push_front
#define mp make_pair
#define vi vector<int>
#define vip vector<pair<int,int> >
#define ff first
#define ss second
#define int long long
#define mod 1000000007
#define BIG 998244353
#define s(t) scanf("%lld",&t)
#define p(t) printf("%lld\n",t)
#define mii map<int,int>
#define MSET(table,i) memset(table, i, sizeof(table))
#define endl '\n'
#define tc int t;cin>>t;while(t--)
#define pi  3.1415926358
#define bits(x) __builtin_popcount(x)
#define minimum(a,n) min_element(a,a+n)-a
#define maximum(a,n) max_element(a,a+n)-a
#define pqbig priority_queue<int>
#define pqsmall priority_queue<pair<int,pii>,vector<pair<int,pii> >,greater<pair<int,pii> > >
#define all(v) v.begin(),v.end()
#define sitr set<int>:: iterator
#define spitr set<pii>:: iterator
#define mitr map<string,int>:: iterator

int toint(const string &s) {stringstream ss; ss << s; int x; ss >> x; return x;}
string tostring ( int number ) {stringstream ss; ss << number; return ss.str();}

typedef tree<pii, null_type, less<pii>, rb_tree_tag,
        tree_order_statistics_node_update>
        new_data_set;

#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl

int32_t main()
{
    fast;
    int h,w;cin>>h>>w;
    if(h==1 or w==1)
    {
        cout<<1;
        return 0;
    }
    int diff=abs(h-w)+1;
    int ans=0;
    ans+=(diff/2+diff%2)*min(h,w);

    int val=min(h,w);
    int terms=(val-1)/2;
    ans+=(val*terms-terms*(terms+1));

    if(diff&1)
        ans+=val*terms-terms*(terms+1);
    else
    {
        terms=val-1-((val-1)/2);
        ans+=val*terms-(terms*terms);
    }

    cout<<ans;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep0(a,b) for(int a=0;a<b;a++)
#define rep1(a,b) for(int a=1;a<=b;a++)
#define repp(a,b,c) for(int a=b;a<c;a++)
#define rev(a,b,c) for(int a=b;a>=c;a--)
#define in insert
#define len length()
#define si size()
#define lb lower_bound
#define ub upper_bound
#define beg begin()
#define end end()
#define vec vector<ll>
#define se set<ll>
#define mults multiset<ll>
#define F first
#define S second
#define pr(a) cout<<a
#define pr2(a,b) cout<<a<<" "<<b
#define get(a) cin>>a
#define nextl cout<<endl
const ll mod = 1000000007;
const ll maxn = 500005;
const ll mm = 1e+18;
ll power(ll x, ll y)
{
    ll res = 1;
    x = x % mod;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % mod;
        y = y>>1;
        x = (x*x) % mod;
    }
    return res;
}
ll ncr(ll n, ll k)
{
    ll C[k+1];
    memset(C, 0, sizeof(C));

    C[0] = 1;

    for (ll i = 1; i <= n; i++)
    {
        for (ll j = min(i, k); j > 0; j--)
            C[j] = (C[j] + C[j-1])%mod;
    }
    return C[k];
}
int CountTriangles(vector <int> A){

    int n=A.si;

    sort(A.beg, A.end);

    int count = 0;

    for( int i = n-1; i >= 1; i--){
        int l = 0, r = i-1;
        while( l < r){
            if( A[l] + A[r] > A[i]){

                // If it is possible with a[l], a[r]
                // and a[i] then it is also possible
                // with a[l+1]..a[r-1],a[r] and a[i]
                count += r - l ;

                //checking for more possible solutions
                r--;
            }
            else

                // if not possible check for
                // higher values of arr[l]
                l++;
        }
    }
    return count;
}
void solve()
{
    int n;
    get(n);
    vector<int> v;
    rep0(i,n){int x;get(x);v.pb(x);}
    int ans=CountTriangles(v);
    pr(ans);
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
       // nextl;
    }
    return 0;
}


Measured memory_bytes: 256
n=int(input())
a=list(map(int, input().split()))
b=list(map(int, input().split()))

plus_l=[]
minus_l=[]
cnt=0
for i in range(n):
    if a[i]<b[i]:
        minus_l.append(b[i]-a[i])
        cnt+=1
    elif a[i]>b[i]:
        plus_l.append(a[i]-b[i])

if sum(minus_l)>sum(plus_l):
    print(-1)
    exit()

sum_minus=sum(minus_l)
tmp_sum_plus=0

plus_l.sort(reverse=True)

for p_i in plus_l:
    if tmp_sum_plus>=sum_minus:
        break
    tmp_sum_plus+=p_i
    cnt+=1
print(cnt)



Measured memory_bytes: 24420
#include<iostream>

using namespace std;

const int MAX = 110;
int A[MAX];
int N;

void Print(int a[], int n)
{
	cout << a[0];
	for (int i = 1; i < n; ++i)
		cout << ' ' << a[i];
	cout << endl;
}
int main()
{
	cin >> N;
	for (int i = 0; i < N; ++i) cin >> A[i];
	Print(A, N);
	int tmp, j;
	for (int i = 1; i < N; ++i)
	{
		tmp = A[i];
		j = i - 1;
		while (j >= 0 && tmp < A[j])
		{
			A[j + 1] = A[j];
			j--;
		}
		A[j + 1] = tmp;
		Print(A, N);
	}
	return 0;
}


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

using namespace std; 

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef pair<LL, LL> PLL;
typedef vector<PLL> VPLL;
typedef priority_queue<int> PQ_DESC;
typedef priority_queue<int, vector<int>, greater<int>> PQ_ASC;
typedef priority_queue<PII> PQ_DESC_PII;
typedef priority_queue<PII, vector<PII>, greater<PII>> PQ_ASC_PII;

#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define MP make_pair
#define SORT_ASC(c) sort(ALL(c))
//#define SORT_DESC(c) sort(ALL(c), greater<typeof(*((c).begin()))>())
#define SORT_DESC(c) sort((c).rbegin(),(c).rend())
#define REV(c) reverse((c).begin(), (c).end())
#define SIZE(a) int((a).size())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ROF(i,a,b) for(int i=(b-1);i>=(a);--i)
#define REP(i,n) FOR(i,0,n)
#define PER(i,n) ROF(i,0,n)

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int LARGE_INT = 1e9+100;
const int INF = 2e9+100;
const LL INF_LL = (LL)INF*(LL)INF;
const int MOD = 1e9+7;

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

LL modpow(LL a, LL n) {
    LL res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

void Main()
{
    string t;cin>>t;
    int n=SIZE(t);

    REP(i,n){
        if(t[i]=='?'){
            t[i]='D';
        }
    }
    cout<<t<<endl;
	return;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
    return 0;
}

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

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using WGraph = vector<vector<pair<int, ll>>>;

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

constexpr int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
constexpr int INF = 1e9;
constexpr int MOD = 1e9 + 7;
constexpr long long LINF = 1e18;
constexpr double EPS = 1e-10;
constexpr double PI = M_PI;

int lis(const std::vector<long long> &vec) {
    int len = (int)vec.size();
    std::vector<long long> dp(len, LINF);
    for (int i=0; i<len; i++) {
        long long tmp = vec.at(i);
        auto iter = std::upper_bound(dp.begin(), dp.end(), tmp);
        *iter = tmp;
    }
    return std::lower_bound(dp.begin(), dp.end(), LINF) - dp.begin();
}

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i=0; i<n; ++i) {
        cin >> a.at(i);
    }

    reverse(a.begin(), a.end());
    cout << lis(a) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    solve();

    return 0;
}


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

int n, k;

bool func(int p, vector<int> w){
  int ans = 0, tn = 0;
  for(int i = 0; i < n; i++){
    ans += w[i];
    if(ans > p){
      tn++;
      ans = w[i];
    }
  }
  tn++;
  //cout << "p:" << p << " tn:" << tn << endl;
  if(tn <= k) return true;
  else return false;
}

void solve(){
  cin >> n >> k;
  vector<int> w(n);
  int maxw = 0;
  for(int i = 0; i < n; i++){
    cin >> w[i];
    maxw = max(w[i], maxw);
  }
  long long int l = maxw, r = 1000000000, m;
  while(l < r){
    m = (l + r) / 2;
    //cout << l << "-" << m << "-" << r << endl;
    if(func(m, w) == true){
      r = m;
    }
    else{
      l = m + 1;
    }
  }
  int ans;
  if(func(m, w) == true) ans = m;
  else ans = m + 1;
  cout << ans << endl;
  return;
}

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



Measured memory_bytes: 3644
#include <iostream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <complex>
#include <cstdio>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

int l,m,n;

int main(){
	while(cin>>l){
		if(!l)return 0;
		int s=0,mo=0;
		while(mo<12&&s<l){
			cin>>m>>n;
			s+=m-n;
			mo++;
		}
		if(s>=l)cout<<mo<<endl;
		else cout<<"NA"<<endl;
		if(mo<12)for(int i=mo;i<12;i++)cin>>m>>n;
	}
}

Measured memory_bytes: 0
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,a+r+r*(.5+3**.5*.5j),b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)


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

int main(){
  int N,ma=0;
  cin>>N;
  vector<int> x(N),y(N),h(N);
  for(int i=0;i<N;i++){
    cin>>x.at(i)>>y.at(i)>>h.at(i);
    ma=max(ma,h.at(i));
  }
  int a=1;
  for(int i=ma;i<=ma+100;i++){
    for(int j=0;j<=100;j++){
      for(int k=0;k<=100;k++){
        for(int l=0;l<N;l++){
          a=1;
          if(i-abs(x.at(l)-j)-abs(y.at(l)-k)==h.at(l)||(i-abs(x.at(l)-j)-abs(y.at(l)-k)<0&&h.at(l)==0)){
          }else{
            a=0;
          }
          if(a==0)break;
          if(l==N-1&&a==1){
            cout<<j<<" "<<k<<" "<<i<<endl;
            return 0;
          }
        }
      }
    }
  }
  
}

Measured memory_bytes: 256
#include <bits/stdtr1c++.h>
#define stat akjcjalsjcjalscj
#define hash ajkscjlsjclajsc
#define next ackjalscjaowjico
#define prev ajcsoua0wucckjsl
#define y1 alkscj9u20cjeijc
#define left lajcljascjljl
#define right aucouasocjolkjl
#define y0 u9cqu3jioajc

using namespace std;
#define TASK "solve"

const int N = 3e5 + 100;
const int module = 1e6 + 3;
const long long Base = 500000004;
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());

long long rand(long long l, long long r){
    return 1LL * (1LL * rnd() * RAND_MAX + rnd()) % (r - l + 1) + l;
}
void doc() {
}

int GCD(int a,int b) {
    return b == 0 ? a : GCD(b,a % b);
}
void solve() {
    int n;
    cin >> n;
    int F[n + 1],a[n + 1];
    F[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        F[i] = GCD(F[i - 1],a[i]);
    }
    int x = 0;
    int Res = F[n];
    for (int i = n; i >= 1; i--) {
        Res = max(Res,GCD(F[i - 1],x));
        x = GCD(x,a[i]);
    }
    cout << Res;
}

int main() {
    srand(time(nullptr));
    ios_base::sync_with_stdio(1); cin.tie(nullptr); cout.tie(nullptr);
    doc();
    solve();
}



Measured memory_bytes: 1024
#include <iostream>
#include <stdio.h>

#define rep(i,min,sup) for(int i=min;i<sup;i++)
#define per(i,min,sup) for(int i=(sup-1);i>=min;i--)
#define swap(a,b) {a+=b;b=a-b;a-=b;}
#define ll long long

using namespace std;

void quickid_sort(int* id,int* X,int left,int right){
  if(right-left<4){
    rep(i,left,right)rep(j,i+1,right)if(X[id[i]]>X[id[j]])swap(id[i],id[j]);
  }else{
    int i=left,j=right-1;
    int pivot=X[id[i]]+(X[id[j]]-X[id[i]])/2;
    while(1){
      while(X[id[i]]<pivot)i++;
      while(X[id[j]]>pivot)j--;
      if(i>=j)break;
      swap(id[i],id[j]);
      i++;j--;
    }
    quickid_sort(id,X,left,i);
    quickid_sort(id,X,j+1,right);
  }
}
void quickid(int* id,int* X,int N){
  /*  sort X[0~N-1]
   *  X[id[i]]=ith minimum X
   */
  rep(i,0,N)id[i]=i;
  quickid_sort(id,X,0,N);
}
void quick(int* X,int N){
  /*  X[i]=ith minimum X
   */
  int id[N],Y[N];
  rep(i,0,N){id[i]=i;Y[i]=X[i];}
  quickid_sort(id,X,0,N);
  rep(i,0,N)X[i]=Y[id[i]];
}

main(){
  int X,Y,A,B,C;
  scanf("%d %d %d %d %d",&X,&Y,&A,&B,&C);
  int P[A+B+C];
  char col[A+B+C];
  rep(i,0,A){scanf("%d",&P[i]);col[i]='R';}
  rep(i,A,A+B){scanf("%d",&P[i]);col[i]='G';}
  rep(i,A+B,A+B+C){scanf("%d",&P[i]);col[i]='W';}
  int M=X+Y;
  int N=A+B+C;
  int max,maxi;
  ll ans=0;
  
  int id[N];
  quickid(id,P,N);
  int i=N;
  while(M){
    maxi=id[--i];
    max=P[maxi];
    if(col[maxi]=='R'&&X){X--;M--;ans+=max;}
    else if(col[maxi]=='G'&&Y){Y--;M--;ans+=max;}
    else if(col[maxi]=='W'){M--;ans+=max;}
    N--;
  }
  printf("%lld",ans);
}

Measured memory_bytes: 2944