akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <fstream>
#include <string>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <assert.h>
using namespace std;

#define NMAX 1001
using point = pair <int, int>;

point v[NMAX];
string sol[NMAX];

bool impossible(const int n) {
    const int p = abs((v[1].first + v[1].second) % 2);
    for (int i = 2; i <= n; i++) {
        if (p != abs((v[i].first + v[i].second) % 2))
            return true;
    }
    return false;
}

int find_k(const int n) {
    int k = 0;
    while (1) {
        const long long M = (1LL << (k + 1)) - 1LL;
        int can = true;
        for (int i = 1; i <= n; i++) {
            long long dist = 0LL + abs(v[i].first) + abs(v[i].second);
            if (dist > M) {
                can = false;
                break;
            }
        }
        if (can) {
            break;
        }
        k++;
    }
    return k;
}

bool is_possible(const long long x, const long long y, const int k) {
    if (k < 0) {
        return x == 0 && y == 0;
    }
    long long M = (1LL << (k + 1)) - 1LL;
    long long dist = 0LL + abs(x) + abs(y);
    return dist <= M;
}

string solve(long long x, long long y, const int k) {
    assert(abs((x + y) % 2) == 1);
    assert(is_possible(x, y, k));

    int dx[] = {0, 0, 1, 0, -1};
    int dy[] = {0, 1, 0, -1, 0};
    char D[] = {'A', 'U', 'R', 'D', 'L'};
    string moves;

    for (int i = k; i >= 0; i--) {
        long long dist = (1LL << i);
        int m;
        for (m = 1; m <= 4; m++) {
            long long xp = x - dist * dx[m];
            long long yp = y - dist * dy[m];
            if (is_possible(xp, yp, i - 1))
                break;
        }
        assert(m <= 4);
        moves.push_back(D[m]);
        x = x - dist * dx[m];
        y = y - dist * dy[m];
    }
    reverse(moves.begin(), moves.end());
    return moves;
}

int main()
{
    ios::sync_with_stdio(false);

    int n;
    // ifstream cin("code.in");
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i].first >> v[i].second;
    }

    if (impossible(n)) {
        cout << "-1\n";
        return 0;
    }

    const int par = abs((v[1].first + v[1].second) % 2);
    if (par == 0) {
        for (int i = 1; i <= n; i++) {
            v[i].second++;
        }
    }
    const int k = find_k(n);
    if (par == 0) {
        cout << k + 2 << '\n' << 1 << " ";
    } else {
        cout << k + 1 << '\n';
    }
    for (int i = 0; i <= k; i++) {
        cout << (1LL << i) << " ";
    }
    cout << '\n';
    for (int i = 1; i <= n; i++) {
        sol[i] = solve(v[i].first, v[i].second, k);
    }
    for (int i = 1; i <= n; i++) {
        if (par == 0)
            cout << "D";
        cout << sol[i] << '\n';
    }

    return 0;
}


Measured memory_bytes: 384
#include<stdio.h>

int main(void)

{
int a, b, d, r;
double f;
scanf("%d %d", &a, &b);

d = a/b;
r = a%b;
	f = (double)a/b;

printf("%d\n", d);
printf("%d\n", r);
printf("%.5f\n", f);
return 0;
}



Measured memory_bytes: 2108
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main() {
	//min(a,b)...a,bの小さいほう
	//max(a,b)...     大きいほう
	int a;
	int b;
	int c;
	int d;
	int e;
	//int num;
	//string s;
	//cin >> s;
	std::cin >> a;
	std::cin >> b;
	std::cin >> c;
	std::cin >> d;
	cout << min(a, b) + min(c, d) << "\n";
	std::cin >> e;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long int
#define ar array
#define mp make_pair
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin>>n;
	int a[n+1] = {0};
	for(int i = 0,j; i<n-1; i++)
	{
		cin>>j;
		a[j]++;
	}
	for(int i = 1; i<=n; i++)
		cout<<a[i]<<endl;
	return 0;
}

Measured memory_bytes: 4360
n=int(input())
counta=0
countw=0
countt=0
countr=0
for i in range(n):
    s=input()
    if s=='AC':
        counta+=1
    elif s=='WA':
        countw+=1
    elif s=='TLE':
        countt+=1
    else:
        countr+=1
print('AC x '+str(counta))
print('WA x '+str(countw))
print('TLE x '+str(countt))
print('RE x '+str(countr))

Measured memory_bytes: 9228
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int N;
    cin >> N;
    vector<int> D1(N), D2(N);
    for(int i = 0; i < N; i++) cin >> D1[i] >> D2[i];
    for(int i = 0; i < N-2; i++){
        if(D1[i] == D2[i] && D1[i+1] == D2[i+1] && D1[i+2] == D2[i+2]){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}


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

#define MAX 100000
typedef long long ll;

int n, k;
ll T[MAX];

int check(ll p){
    int i = 0;
    for(int j = 0; j < k; j++){
        ll s = 0;
        while(s + T[i] <= p){
            s += T[i];
            i++;
            if(i == n)  return n;
        }
    }
    return i;
}

int solve(){
    ll left = 0;
    ll right = 100000*10000;
    ll mid;
    while(right - left > 1){
        mid = (right + left) / 2;
        int v = check(mid);
        if(v >= n){
            right = mid;
        }else{
            left = mid;
        }
    }
    return right;
}

int main(){
    cin >> n >> k;   
    for(int i = 0; i < n; i++)  cin >> T[i];
    ll ans = solve();
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3868
def solve():
  n, y = [int(x) for x in input().split()]

  for man in range(n + 1):
    for gos in range(n + 1 - man):
      sen = n - man - gos
      if man * 10000 + gos * 5000 + sen * 1000 == y:
        print(man, gos, sen)
        return
  print(-1, -1, -1)

solve()


Measured memory_bytes: 3060
#charsで文字列をEnumeratorオブジェクトを作り、
#to_aで配列にする
a = gets.strip.chars.to_a
while a.size > 1 do
#popの引数は後ろからその数だけ取り除く
  unless a.shift == a.pop
    puts 'No'
    exit
  end
end
puts 'Yes'


Measured memory_bytes: 1788
import sys
from collections import Counter
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N, K, Q = MAP()
A = [0]*Q
for i in range(Q):
    A[i] = INT()
c = Counter(A)
for i in range(N):
    if c[i+1] > Q-K:
        print('Yes')
    else:
        print('No')

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

const int _ = 153;
int N , K , M;
void inc(int &a , int b){a = a + b >= M ? a + b - M : a + b;}

namespace solve1{
#define PII pair < int , int >
	map < PII , int > dp[_][_][_];

	void ins(int i , int j , int k , int pj , int pk , int val){
	}
	
	void main(){
		dp[0][0][0][PII(N + 1 , N + 1)] = 1;
		for(int i = 0 ; i < N ; ++i){
			for(int j = 0 ; j <= N ; ++j)
				for(int k = 0 ; k <= N ; ++k)
					for(auto t : dp[i][j][k]){
						int pj = t.first.first , pk = t.first.second , val = t.second;
						if(!(i & 1)){
							inc(dp[i + 1][0][k][PII(N + 1 , pk)] , val);
							if(i + 1 != pj)
								if(i + 2 - 2 * k + K <= i + 1 && i + 1 - 2 * j + K > i)
									inc(dp[i + 1][j + 1][k][PII(pj , min(pk , i + 1 - 2 * j + K))] , val);
								else inc(dp[i + 1][j + 1][k][PII(pj , pk)] , val);
						}
						else{
							inc(dp[i + 1][j][0][PII(pj , N + 1)] , val);
							if(i + 1 != pk)
								if(i + 2 - 2 * j + K <= i + 1 && i + 1 - 2 * k + K > i)
									inc(dp[i + 1][j][k + 1][PII(min(pj , i + 1 - 2 * k + K) , pk)] , val);
								else inc(dp[i + 1][j][k + 1][PII(pj , pk)] , val);
						}
					}
		}
		int cnt = 0;
		for(int j = 0 ; j <= N ; ++j) for(int k = 0 ; k <= N ; ++k) for(auto t : dp[N][j][k]) inc(cnt , t.second);
		cout << cnt;
	}
}

namespace solve2{
	int dp[153];
	void main(){
		dp[0] = 1; int len = K / 2 + 1;
		for(int i = 1 ; i <= N / 2 + 1 ; ++i) dp[i] = (dp[i - 1] * 2ll - (i >= len ? dp[i - len - (i != len)] : 0) + M) % M;
		cout << 1ll * dp[N / 2] * dp[N / 2 + (N & 1)] % M;
	}
}

int main(){
	cin >> N >> K >> M;
	if(K & 1) solve1::main(); else solve2::main();
	return 0;
}

Measured memory_bytes: 221696
n,*h=map(int,open(0).read().split())
dp=[0]*n
dp[0]=0
dp[1]=abs(h[0]-h[1])
for i in range(2,n):
  dp[i]=min(dp[i-2]+abs(h[i-2]-h[i]),dp[i-1]+abs(h[i-1]-h[i]))
print(dp[-1])  


Measured memory_bytes: 13876
N = int(input())
P = [int(x) for x in input().split()]
Q = [int(x) for x in input().split()]
def get_order(N, src):
    MOD = 10**9+7

    bit = [0] * (N+1)
    def bit_add(a,w):
        x = a
        while x <= N:
            bit[x] += w
            x += (x & -x)

    def bit_sum(a):
        x = a
        ret = 0
        while x > 0:
            ret += bit[x]
            x -= (x & -x)
        return ret

    ans = fac = 1
    for i in range(N-1,-1,-1):
        a = src[i]
        ans += (bit_sum(a) * fac) % MOD
        bit_add(a,1)
        fac = (fac * (N-i)) % MOD

    return ans % MOD
print(abs(get_order(N,P)-get_order(N,Q)))


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

int main(){
  long long x;
  cin >> x;
  for (int b = -120; b < 120; b++){
    for (int a = b; a < 120; a++){
      if ( a*a*a*a*a - b*b*b*b*b == x ){
        cout << a << " " << b << endl;
        return 0;
      }
    }
  }
}

Measured memory_bytes: 3636
#include <stdio.h>
#pragma warning(disable:4996)

int main(void) {
	int height[10];
	int i, j,k,l;
	int con;
	for (i = 0; i < 10; i++) {
		scanf("%d", &height[i]);
	}
	for (j = 0; j < 9; j++) {
		for (k = j+1; k < 10; k++) {
			if (height[j] < height[k]) {
				con = height[j];
				height[j] = height[k];
				height[k] = con;
			}
		}
	}
	for (l = 0; l < 3; l++) {
		printf("%d\n", height[l]);
	}


}

Measured memory_bytes: 1768
h, w = gets.split.map(&:to_i)
arr = Array.new(w){[0, 0]}
ans = 0
h.times do |i|
    s = gets
    k = 0
    w.times do |j|
        if s[j] == "#"
            k.upto(j-1) {|l| arr[l][1] = j - k if arr[l][1] < j - k}
            k = j + 1
            ans < (sum = arr[j][0] + arr[j][1]) and ans = sum
            arr[j] = [0, 0]
        else
            arr[j][0] += 1
        end
    end
    k.upto(w-1) {|l| arr[l][1] = w - k if arr[l][1] < w - k}
end

arr.each {|a, b| ans = a + b if ans < a + b}
puts ans - 1

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

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


  if (s[1] == s[2] && (s[1] ==s[0] || s[2] ==s[3])){
  cout << "Yes";
  }else{
  cout << "No";
  }
    return 0;
}






Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#ifdef LOCAL
#include<debug.h>
#else
#define db(...) 21
#endif
#define sz(a) ((int)(a).size())
#define uset unordered_set
#define umap unordered_map
#define A(x) (x).begin(),(x).end()
#define fo(i,n) for(int i=0;i<(int)n;i++)
#define Fo(i,k,n) for(int i=k;k<n?i<=(int)n:i>=(int)n;k<n?i++:i--)
#define input(v,n) fo(i,n)cin>>v[i]
using vi = vector<int>;
using vpi = vector<pair<int,int>>;
using pi = pair<int,int>;

const int nax = 1e5+7;
const int mod = 1e9+7; //1e9+2667 :: 0xcf : inf, 0xc0 -inf
const int inf = numeric_limits<int> :: max() - (int)9e6;
// ===================== MANASH =================== //
int n;
vpi v;
int dp[10001][1001];
int mindp( int h, int i) {

	if ( h <= 0 ) return 0;
	if ( i == n ) return inf;
	int &ans = dp[h][i];
	if ( ans != -1 ) return ans;
	ans = inf;
	return ans = min(mindp(h,i+1),mindp(h-v[i].first,i)+v[i].second);
}

void test() {
	int H;
	cin >> H >> n;
	memset(dp,-1,sizeof(dp));
	v.resize(n);
	for( int i = 0; i < n; i++) {
		cin >> v[i].first >> v[i].second;
	}
	cout << mindp(H,0);
}

signed main() {

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

	#ifdef LOCAL
	freopen("input.txt","r",stdin);
	#endif

	int T = 1;
	// cin >> T;
	while(T--) {
		test();
		cout << "\n";
	}
	return 0;

}

Measured memory_bytes: 82372
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;

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

const int inf = 1e9 + 1;
const double eps = 1e-9;
const int MAXN = 301;

int n;
int a[MAXN];
double dp[MAXN][MAXN][MAXN];
int br[4];

double rek(int a, int b, int c){

    if (dp[a][b][c] != -1) return dp[a][b][c];

    double ret = 0;

    if (a > 0) ret += (double)a/n*(1+rek(a-1, b, c));
    if (b > 0) ret += (double)b/n*(1+rek(a+1, b-1, c));
    if (c > 0) ret += (double)c/n*(1+rek(a, b+1, c-1));
    ret += (double)(n-a-b-c)/n;
    ret = (double)ret/(1 - (double)(n-a-b-c)/n);

    return dp[a][b][c] = ret;

}

int main(){

    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> a[i];
        if (a[i] == 1) br[1]++;
        if (a[i] == 2) br[2]++;
        if (a[i] == 3) br[3]++;
    }

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            for (int k = 0; k <= n; k++)
                dp[i][j][k] = -1;

    dp[0][0][0] = 0;

    cout << setprecision(15) << fixed << rek(br[1], br[2], br[3]);

    return 0;

}

Measured memory_bytes: 213376
import java.util.*;

public class Main {    
    public static void main(String[] args){        
        Scanner sc = new Scanner(System.in);                
         
        String A = sc.next();
        String B = sc.next();
        
        
        if(A.length() > B.length()){
           System.out.println("GREATER");   
           return; 
        }else if(A.length() < B.length()){
           System.out.println("LESS");
           return;
        }else if(A.length() == B.length()){
           for(int i = 0 ;i < A.length();i++){ 
               char a = A.charAt(i);                        
               char b = B.charAt(i);
             
               int x = a - '0';
               int y = b - '0';
                              
               if(x > y){
                   System.out.println("GREATER");
                   return;
               }else if(y > x){
                   System.out.println("LESS");
                   return;
               }                                  
             
           }
           System.out.println("EQUAL");
           return;
        }
        
    }            
}

        

Measured memory_bytes: 21844
using System;

namespace ABC090_A
{
    class Program
    {
        static void Main(string[] args)
        {
            var c1 = Console.ReadLine();
            var c2 = Console.ReadLine();
            var c3 = Console.ReadLine();
            Console.WriteLine($"{c1[0]}{c2[1]}{c3[2]}");
        }
    }
}


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

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

#define p_ary(ary,a,b) do { cout << "["; for (int count = (a);count < (b);++count) cout << ary[count] << ((b)-1 == count ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

template<typename T1,typename T2>ostream& operator<<(ostream& os,const pair<T1,T2>& a) {os << "(" << a.first << ", " << a.second << ")";return os;}

const char newl = '\n';

int main() {
    int k;
    cin >> k;
    ll ng = 0,ok = 3234566667;
    while (ok-ng > 1) {
        ll mid = (ok+ng)/2;
        string s = to_string(mid);
        int n = s.size();
        bool f = true;
        vector<vector<int>> dp(n+1,vector<int>(10,0));
        for (int i = 0;i < n;++i) {
            if (i) for (int j = 1;j < 10;++j) dp[i+1][j]++;
            else for (int j = 1;j < s[i]-'0';++j) dp[i+1][j]++;
            if (i && f) {
                if (s[i-1]-'0' && s[i-1]-1 < s[i]) dp[i+1][s[i-1]-'0'-1]++;
                if (s[i-1] < s[i]) dp[i+1][s[i-1]-'0']++;
                if (s[i-1]-'0' < 9 && s[i-1]+1 < s[i]) dp[i+1][s[i-1]-'0'+1]++;
            }
            for (int j = 0;j < 10;++j) {
                if (j) dp[i+1][j-1] += dp[i][j];
                dp[i+1][j] += dp[i][j];
                if (j < 9) dp[i+1][j+1] += dp[i][j];
            }
            if (i && abs(s[i-1]-s[i]) > 1) f = false;
        }
        int sum = f;
        for (int i = 0;i < 10;++i) sum += dp[n][i];
        (sum < k ? ng : ok) = mid;
    }
    cout << ok << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,x=1,y=0,vy=0,z=0;
    cin>>a>>b;
    int c[b],d[b];
    for(int i=0;i<b;i++){
        cin>>c[i]>>d[i];
        if(y<c[i]) y=c[i];
    }
    while(1){
        vy=y;
        y=0;
        for(int i=0;i<b;i++){
            if(vy>=d[i]){
                c[z]=c[i];
                d[z]=d[i];
                if(y<c[i]) y=c[i];
                z++;
            }
        }
        if(z) x++;
        else break;
        z=0;
    }
    cout<<x<<endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define ADD(a, b) a = (a + b) % mod
#define SUB(a, b) a = (a+mod-b)%mod
#define MUL(a, b) a = (a * b) % mod
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define fi first
#define se second
typedef pair<int,int> P;
typedef pair<int, P> PP;
typedef vector<int> vi;
typedef deque<int> dq;
const int inf = 1e9+7;
const int INF = 1e18+7;

int ok(string str, int n){
	char c = str[0];
	rep(i,n)if(str[i] != c)return 0;
	return 1;
}

int solve(string str, char c){
	int n = str.size(), res = 0;
	drep(i,n,0){
		if(ok(str, i))break;
		rep(j,i-1){
			if(str[j] == c or str[j+1] == c)str[j] = c;
		}
		res++;
	}
	//cout << str << endl;
	return res;
}

signed main(){
	string str;
	cin >> str;
	int n = str.size(), ans = INF;
	rep(i,n){
		chmin(ans, solve(str, str[i]));
	}
	printf("%lld\n", ans);
	return 0;
}







Measured memory_bytes: 256
# N = gets.chomp.to_i
N, M = gets.chomp.split.map(&:to_i)
mostL = 0
mostR = N + 1
M.times do 
  l, r = gets.chomp.split.map(&:to_i)
  if mostL < l
    mostL = l  # shrink
  end
  if r < mostR
    mostR = r  # shrink
  end
end
# A = Array.new(N + 1, 0)  # 0 means no trap, 1 means existence of trap. 1-indexed

# Now, L, L + 1, .. R can be used

if mostR >= mostL
  p mostR - (mostL - 1)
else
  p 0
end


Measured memory_bytes: 1788
#include <algorithm>
#include <cmath>
#include <vector>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <ctype.h>
#include <climits>
#include <queue>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)



int main(){
	int x,y;
	cin >> x >> y;
	
	int tsu,ka;
	
	ka = abs((y-x*2)/2);
	tsu  = abs((x*4-y)/2);
	//cout << ka << " "<<tsu<<endl;
	if(ka+tsu==x && ka*4+tsu*2==y){
		cout << "Yes\n";
	}else{
		cout << "No\n";
	}
	
	return 0;
	
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n; cin>>n;
  int d; cin>>d;
  vector<vector<int>> X(n,vector<int>(d));
  rep(i,n) rep(j,d) cin>>X.at(i).at(j);
  int ans=0;
  rep(i,n-1){
    for(int j=i+1;j<n;j++){
      int num=0;
      rep(k,d){
        int diff = abs(X.at(i).at(k)-X.at(j).at(k));
        num+=diff*diff;
      }
      bool flag=0;
      rep(k,num+1){
        if(k*k==num) flag=true;
      }
      if(flag) ans++;
    }
  }
  cout<<ans<<endl;      
}

Measured memory_bytes: 256
import collections

n=int(input())
arr=[int(input()) for _ in range(n)]
arr=sorted(arr)
if n%2==1:
  q=collections.deque()
  q.append(arr[0])
  l=1
  r=n-1
  move=1
  while 1:
    q.appendleft(arr[r])
    r-=1
    q.append(arr[r])
    r-=1
    move+=2
    if move==n:
      break
    q.appendleft(arr[l])
    l+=1
    q.append(arr[l])
    l+=1
    move+=2
    if move==n:
      break
  q=list(q)
  ans1=0
  for i in range(n-1):
    ans1+=abs(q[i+1]-q[i])
  q=collections.deque()
  q.append(arr[-1])
  l=0
  r=n-2
  move=1
  while 1:
    q.appendleft(arr[l])
    l+=1
    q.append(arr[l])
    l+=1
    move+=2
    if move==n:
      break
    q.appendleft(arr[r])
    r-=1
    q.append(arr[r])
    r-=1
    move+=2
    if move==n:
      break
  q=list(q)
  ans2=0
  for i in range(n-1):
    ans2+=abs(q[i+1]-q[i])
  ans=max(ans1,ans2)
  print(ans)
else:
  q=collections.deque()
  q.append(arr[0])
  l=1
  r=n-1
  move=1
  while 1:
    if n-move==1:
      break
    q.appendleft(arr[r])
    r-=1
    q.append(arr[r])
    r-=1
    move+=2
    if n-move==1:
      break
    q.appendleft(arr[l])
    l+=1
    q.append(arr[l])
    l+=1
    move+=2
  q=list(q)
  ans1=0
  for i in range(n-2):
    ans1+=abs(q[i+1]-q[i])
  ans1+=max(abs(arr[l]-q[0]),abs(arr[l]-q[-1]))
  q=collections.deque()
  q.append(arr[-1])
  l=0
  r=n-2
  move=1
  while 1:
    if n-move==1:
      break
    q.appendleft(arr[l])
    l+=1
    q.append(arr[l])
    l+=1
    move+=2
    if n-move==1:
      break
    q.appendleft(arr[r])
    r-=1
    q.append(arr[r])
    r-=1
    move+=2
  q=list(q)
  ans2=0
  for i in range(n-2):
    ans2+=abs(q[i+1]-q[i])
  ans2+=max(abs(arr[r]-q[0]),abs(arr[r]-q[-1]))
  ans=max(ans1,ans2)
  print(ans)

Measured memory_bytes: 8908
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

const mod = 1000000007

var fracMemo = []int{1, 1}

func mfrac(n int) int {
	if len(fracMemo) > n {
		return fracMemo[n]
	}
	if len(fracMemo) == 0 {
		fracMemo = append(fracMemo, 1)
	}
	for len(fracMemo) <= n {
		size := len(fracMemo)
		fracMemo = append(fracMemo, fracMemo[size-1]*size%mod)
	}
	return fracMemo[n]
}

func main() {
	sc.Split(bufio.ScanWords)

	N, M := getInt(), getInt()
	ans := 0
	if asub(M, N) > 1 {
		ans = 0
	} else {
		ans = (mfrac(N) * mfrac(M)) % mod
		if M == N {
			ans = (ans * 2) % mod
		}
	}
	out(ans)
}


Measured memory_bytes: 5376
#include<iostream>
int main(){
	int n;
	std::cin >> n;
	if (n >= 64) {
		std::cout << "64" << std::endl;
	}
	else if (n >= 32) {
		std::cout << "32" << std::endl;
	}
	else if (n >= 16) {
		std::cout << "16" << std::endl;
	}
	else if (n >= 8) {
		std::cout << "8" << std::endl;
	}
	else if (n >= 4) {
		std::cout << "4" << std::endl;
	}
	else if (n >= 2) {
		std::cout << "2" << std::endl;
	}
	else {
		std::cout << "1" << std::endl;
	}
}

Measured memory_bytes: 256
package main

// Solution for https://atcoder.jp/contests/abc173/tasks/abc173_c

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

type contest struct {
	in  io.Reader
	out io.Writer
}

func (con *contest) Scan(a ...interface{}) (int, error) {
	return fmt.Fscan(con.in, a...)
}
func (con *contest) Scanln(a ...interface{}) (int, error) {
	return fmt.Fscanln(con.in, a...)
}
func (con *contest) Scanf(f string, a ...interface{}) (int, error) {
	return fmt.Fscanf(con.in, f, a...)
}
func (con *contest) Print(a ...interface{}) (int, error) {
	return fmt.Fprint(con.out, a...)
}
func (con *contest) Println(a ...interface{}) (int, error) {
	return fmt.Fprintln(con.out, a...)
}
func (con *contest) Printf(f string, a ...interface{}) (int, error) {
	return fmt.Fprintf(con.out, f, a...)
}
func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()
	con := &contest{in: in, out: out}
	con.main()
}

func (con *contest) main() error {
	var H, W, K int
	con.Scan(&H, &W, &K)
	M := make([]string, H)
	for h := 0; h < H; h++ {
		con.Scan(&M[h])
	}
	c := 0
	for i := 0; i < 1<<H; i++ {
		for j := 0; j < 1<<W; j++ {
			k := 0
			for h := 0; h < H; h++ {
				if i&(1<<h) != 0 {
					continue
				}
				for w := 0; w < W; w++ {
					if j&(1<<w) != 0 {
						continue
					}
					if M[h][w] == '#' {
						k++
					}
				}
			}
			if k == K {
				c++
			}
		}
	}
	con.Println(c)
	return nil
}


Measured memory_bytes: 1848
#include <bits/stdc++.h>
using namespace std;
int INF = 10000000;
int main(){
  string S;
  cin >> S;
  int L = S.size();
  vector<int> p;
  vector<char> op;
  for (int i = 0; i < L; i++){
    if ('0' <= S[i] && S[i] <= '9'){
      p.push_back(i);
    }
    if (S[i] == '+' || S[i] == '-'){
      op.push_back(S[i]);
    }
  }
  int N = p.size();
  vector<vector<int>> dpmax(N + 1, vector<int>(N + 1, -INF));
  vector<vector<int>> dpmin(N + 1, vector<int>(N + 1, INF));
  for (int i = 0; i < N; i++){
    dpmax[i][i + 1] = S[p[i]] - '0';
    dpmin[i][i + 1] = S[p[i]] - '0';
  }
  for (int r = 2; r <= N; r++){
    for (int i = 0; i <= N - r; i++){
      int j = i + r;
      for (int k = i + 1; k < j; k++){
        bool ok = true;
        if (k == i + 1){
          if (S[p[i] + 1] == ')'){
           ok = false;
          }
        }
        if (k == j - 1){
          if (S[p[k] - 1] == '('){
            ok = false;
          }
        }
        if (ok){
          if (op[k - 1] == '+'){
            dpmax[i][j] = max(dpmax[i][j], dpmax[i][k] + dpmax[k][j]);
            dpmin[i][j] = min(dpmin[i][j], dpmin[i][k] + dpmin[k][j]);
          }
          if (op[k - 1] == '-'){
            dpmax[i][j] = max(dpmax[i][j], dpmax[i][k] - dpmin[k][j]);
            dpmin[i][j] = min(dpmin[i][j], dpmin[i][k] - dpmax[k][j]);
          }
        }
      }
    }
  }
  cout << dpmax[0][N] << endl;
}


Measured memory_bytes: 3272
#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
// using namespace atcoder;
using ll = long long;
using ull = unsigned long long;
#define REP(i,n) for (ll i = 0; i < (n); ++i)
#define RREP(i, n) for (ll i = (n) - 1; i >= 0; --i)
#define ALL(v) (v).begin(), (v).end()
template<class T>
using reverse_priority_queue = priority_queue<T, vector<T>, greater<T>>;


int main(){
    string s;
    cin >> s;
    if(s.back() == 's'){
        s += "es";
    }else{
        s += "s";
    }
    cout << s << endl;
    return 0;
}


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

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

    int l, d[n]={0},ans[n]={0}, x=0;

    for (int i=0; i<n; i++){
        std::cin >> d[i];
        for (int j=0; j<d[i]; j++){
            std::cin >> l;
            ans[l-1]++;
        }
    }
    for (int i=0; i<n; i++){
        if(ans[i] == 0){
            x++;
        }
    }
    std::cout << x;
}

Measured memory_bytes: 3592
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n,n){
        bool flag=0;
        double result[4001]={};
        for(int i=0,con;i<n;i++){
            double sale,num;
            cin>>con>>sale>>num;
            sale/=1000;num/=1000;
            result[con]+=sale*num;
            if(result[con]>=1){
                cout<<con<<endl;
                result[con]=-50;
                flag=1;
            }
        }
        if(!flag)cout<<"NA"<<endl;
    }
}

Measured memory_bytes: 1268
#include <bits/stdc++.h>
//#include <ext/numeric>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define oo 0x3f3f3f3f
#define OO 0x3f3f3f3f3f3f3f3f
#define popcount(n) __builtin_popcount(n)
#define popcountll(n) __builtin_popcountll(n)

//bool flag = __builtin_add_overflow(a , b , &tmp);
//bool flag = __builtin_mul_overflow(a , b , &tmp);
//bool flag3= __builtin_sub_overflow(a , b , &tmp);

using namespace std;
//using namespace __gnu_cxx;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const double PI = acos(-1.0), EPS = 1e-12;
const long long inf = 2e12 + 12;
const int MAXN = 250005, MAXM = 102, Mod = 1000000007 , MAXLog = 20;


int main() {
#ifndef ONLINE_JUDGE
//    freopen("input.txt", "rt", stdin);
//    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0), cout.precision(9), cout << fixed;

    int a, b;
    cin >> a >> b;

    int c = abs(a - b);
    if (c % 2 == 0)
        cout << c / 2 + min(a, b) << '\n';
    else
        cout << "IMPOSSIBLE\n";


    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main()
{
	int i,j,k;
	int data[10+1];
	for(i=0;i<10;i++){
		scanf("%d",&data[i]);
	}
	for(i=0;i<9;i++){
		for(j=i+1;j<10;j++){
			if(data[i]<data[j]){
				k=data[i];
				data[i]=data[j];
				data[j]=k;
			}
		}
	}
	for(i=0;i<3;i++){
		printf("%d\n",data[i]);
	}
	return 0;
}

Measured memory_bytes: 600
#include <cmath>
#include <vector>
#include <map>
#include <functional>
#include <queue>
#include <iostream>
#include <string>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <cstdint>
#include <climits>
#include <unordered_set>

using namespace std;

#define ll long long int
#define ti4 tuple<int,int,int,int>
#define pii pair<ll,ll>
#define REP(x,n) for(int x = 0;x < n;x++)

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

struct UnionFind {
    vector<int> data;
    UnionFind(int size) : data(size, -1) { }
    bool unionSet(int x, int y) {
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = x;
        }
        return x != y;
    }
    bool findSet(int x, int y) {
        return root(x) == root(y);
    }
    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    int size(int x) {
        return -data[root(x)];
    }
};

const ll mod = (ll)(1e9+7);

struct SimpleHash {
    size_t operator()(const std::pair<ll, ll>& p) const {
        return p.first * mod + p.second;
    }
};

int main()
{
    ll h,w,n;
    cin >> h >> w >> n;
    unordered_set<pii, SimpleHash> s;
    unordered_set<pii, SimpleHash> dot;
    vector<pii> hi;
    for(int i = 0;i < n;i++)
    {
        ll y, x;
        cin >> y >> x;
        y--;
        x--;
        dot.insert(make_pair(x,y));
        for(ll dx = max((ll)1L, (ll)(x-1L)); dx <= min(w-2L, x+1L);dx++)
        {
            for(ll dy = max((ll)1L, (ll)(y-1L)); dy <= min(h-2L, y+1L);dy++)
            {
                pii d = make_pair(dx, dy);
                if(s.find(d) == s.end())
                {
                    hi.push_back(d);
                    s.insert(make_pair(dx, dy));
                }
            }
        }
    }
    map<pii, int> counts;
    ll cs[10];
    fill(cs, cs + 10, 0);
    for(auto& e: hi)
    {
        ll x = e.first;
        ll y = e.second;
        int c = 0;
        for(ll dx = max((ll)0L, (ll)(x-1L)); dx <= min(w-1L, x+1L);dx++)
        {
            for(ll dy = max((ll)0L, (ll)(y-1L)); dy <= min(h-1L, y+1L);dy++)
            {
                if(dot.find(make_pair(dx, dy)) != dot.end())
                {
                    c++;
                }
            }
        }
        counts[e] = c;
        cs[c]++;
    }
    ll nz = 0;
    for(int i = 1;i < 10;i++)
    {
        nz += cs[i];
    }
    cs[0] = (w-2) * (h-2) - nz;
    for(int i = 0;i < 10;i++)
    {
        cout << cs[i] << endl;
    }    
    return 0;
}

Measured memory_bytes: 126708
#include <bits/stdc++.h>
#define mod 1000000007
#define pb push_back
#define ll long long
#define mp make_pair
using namespace std;
int main(){
	ll n,m;
	cin>>n>>m;
	ll ans = 0;
	ans += (1900*m + 100*(n-m)) * (1<<m);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <deque>
using namespace std;

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

const ll mod=1000000007;

ll per(ll k){
  if(k<=1)return 1;
  return k*per(k-1)%mod;
}

int main(){
  ll n,m,r,ans;
  cin>>n>>m;
  if(abs(n-m)>1){
    cout<<0<<endl;
    return 0;
  }else if(abs(n-m)==1){
    r=1;
  }else{
    r=2;
  }
  ans=per(n)*per(m)%mod;
  cout<<ans*r%mod<<endl;
  return 0;
}


Measured memory_bytes: 1792
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = 0
l = A[0]
for i in range(N):
    r = A[i + 1]
    cur = B[i]
    # print(l, r, cur)
    ans += min(l + r, cur)
    l = max(r - max(cur - l, 0), 0)  # めちゃくちゃ整理するとこの形の式になる
print(ans)

Measured memory_bytes: 82020
# -*- coding: utf-8 -*-
"""
A - Diagonal String
https://beta.atcoder.jp/contests/abc090/tasks/abc090_a

"""
import sys
from sys import stdin
input = stdin.readline


def main(args):
    data = []
    for _ in range(3):
        data.append(input().strip())

    print(data[0][0] + data[1][1] + data[2][2])


if __name__ == '__main__':
    main(sys.argv[1:])


Measured memory_bytes: 3060
N,K=map(int, input().split())
A=list(map(int, input().split()))
A=sorted(A)
import numpy as np
A=np.array(A,dtype="int64")
Z=A[A==0]
H=A[A<0]
S=A[A>0]
l,r=-10**19,10**19
while r-l>1:
  mid=(r+l)//2
  cnt=0
  cnt+=A.searchsorted(mid//S,side="right").sum()
  cnt+=(N-A.searchsorted((-mid-1)//(-H),side="right")).sum()
  cnt-=np.count_nonzero(A*A<=mid)
  if mid>=0:
    cnt+=len(Z)*N 
  cnt//=2
  if cnt>=K:
    r=mid
  else:
    l=mid 
print(r)

Measured memory_bytes: 35200
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define mp make_pair
#define fi fisrt
#define se second

using namespace std;
const int N=1e5+5;
const int mod=1e9+7;
const int inf=0x3f3f3f3f3f3f3f;

int ksm(int xx,int yy,int zz)
{
	int ret;
	while (yy)
	{
		if (yy&1) ret=(ret*xx) % zz;
		xx=(xx*xx)%zz;
		yy>>=1;
	}
	return ret;
}

signed main()
{
	string str;
	cin>>str;
	int len=str.length();
	int ans=0;
	for (int i=0;i<len;i++)
		ans+=signed(str[i])-signed('0');
	if (ans%9==0) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}


Measured memory_bytes: 3752
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define E "\n"

using namespace std;
const long long MOD = (long long)1e9 + 7;

int n, k, a[200009];
long long s[200009];

int main()
{
	//ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		s[i] = a[i];
		if (i) s[i] += s[i - 1];
	}
	long long ans = 0;
	for (int i = k - 1; i < n; i++) {
		long long tmp = s[i];
		if (i >= k) tmp -= s[i - k];
		ans = max(ans, tmp);
	}
	double p = ((double)ans) / 2;
	p += 0.5 * k;
	cout << setprecision(20) << p << E;
	//system("pause");
	return 0;
}

Measured memory_bytes: 2560
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <bitset>    // bitset
#include <deque>     // deque
#include <iomanip>   //setprecsion
#include <iostream>  // cout, endl, cin
#include <map>       // map
#include <queue>     // queue, priority_queue
#include <set>       // set
#include <stack>     // stack
#include <string>    // string, to_string, stoi
#include <tuple>     // tuple, make_tuple
#include <utility>   // pair, make_pair
#include <vector>    // vector

#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath>  //sin, cos, tan

using namespace std;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rrep(i, n) for (ll i = (n - 1); i >= 0; --i)
#define blank(ans) cout << (ans) << " ";
#define mp(p, q) make_pair(p, q)
#define mt(p, q, r) make_tuple(p, q, r)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef string str;

typedef vector<ll> vll;
typedef vector<ld> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<str> vs;
typedef vector<vector<ll>> vvll;
typedef vector<vector<ld>> vvd;
typedef vector<vector<bool>> vvb;
typedef vector<vector<char>> vvc;
typedef vector<vector<str>> vvs;
typedef vector<pair<ll, ll>> vpll;
typedef vector<tuple<ll, ll, ll>> vtlll;

const ld PI = acos(-1.0);
const ll MAX = 9000000000000000000;
const ll MIN = -9000000000000000000;
const ld DMAX = 4500;
const ld DMIN = -4500;
const ll MOD = 1000000007;

template <typename T>
void fin(T a)
{
  cout << a << endl;
  exit(0);
}

//桁数
ll GetDigit(ll num)
{
  return log10(num) + 1;
}

//約数全列挙
vector<ll> enum_div(ll n)
{
  vector<ll> ret;
  for (ll i = 1; i * i <= n; ++i)
  {
    if (n % i == 0)
    {
      ret.push_back(i);
      if (i * i != n)
      {
        ret.push_back(n / i);
      }
    }
  }
  sort(begin(ret), end(ret));
  return ret;
}

//累乗(xのn乗%mod)
ll modpow(ll x, ll n, ll mod = MAX)
{
  ll res = 1;
  while (n > 0)
  {
    if (n & 1)
      res = res * x % mod;
    x = x * x % mod;
    n >>= 1;
  }
  return res;
}

//階乗
ll factorial(ll n)
{
  if (n > 0)
    return n * factorial(n - 1);
  else
    return 1;
}

ll modinv(ll a, ll mod)
{
  ll b = mod, u = 1, v = 0;
  while (b)
  {
    ll t = a / b;
    a -= t * b;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  u %= mod;
  if (u < 0)
    u += mod;
  return u;
}

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

ll lcm(ll a, ll b)
{
  return a * b / gcd(a, b);
}

void Main()
{
  ll n; cin >> n;
  vll x(n), y(n); rep(i, n) cin >> x[i] >> y[i];
  vll loot(n); rep(i, n) loot[i] = i;
  ld Sum = 0, T = 0.;
  do
  {
    for(ll i = 1;i < n;i++)
    {
      ll X = x[loot[i - 1]] - x[loot[i]], Y = y[loot[i - 1]] - y[loot[i]];
      Sum += sqrt(X*X+Y*Y);
    }
    T++;
  }while(next_permutation(all(loot)));
  T *= 1.;
  fin(Sum / T);
}

//前処理
int main()
{
  //ios::sync_with_stdio(false);
  //cin.tie(0);
  cout << fixed << setprecision(20); //高精度少数表示
  //cout << setfill('0') << internal << setw(4); 0埋め４桁
  Main();
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
// #define pb push_back
//
// int dp[200001];
//
//
// int a[200001];
// int b[200001];
//
// int main()
// {
//     int n;
//     cin>>n;
//     for(int i=0;i<n;i++){
//         cin>>a[i];
//         cin>>b[i];
//     }
//     dp[0]=1;
//     for(int i=1;i<n;i++)
//     {
//         int x=0;
//         for(int j=0;j<i;j++)
//         {
//             if((a[i]*a[j] + b[i]*b[j]) != 0){
//                 x+=dp[j];
//             }else{
//                 x-=dp[j];
//             }
//         }
//         dp[i] = 1 + 2*x;
//     }
//     cout<<dp[n-1]<<endl;
// }
//

































#define pi 3.14159265358979323846
int main()
{
    double a,b,h,m;
    cin>>a>>b>>h>>m;
    double  angle1 = (pi / 6.0) * (h + m/60.0);
    double angle2 = (pi / 30.0) * m;
    double anglebtwn;
    if(angle1 > angle2){
        anglebtwn = angle1 - angle2;
    }
    else{
        anglebtwn = angle2 - angle1;
    }
    if(anglebtwn > 180)anglebtwn -= 180;
    cout<<setprecision(15)<< sqrt( (a*a + b*b - (2*a*b*cos(anglebtwn))) );

}


Measured memory_bytes: 4220
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vlli vector<ll>
#define vi vector<int>
#define vs vector<string>
#define vplli vector< pair< ll,ll> >
#define plli pair< ll,ll >
#define vps vector< pair< string, string> >
#define vpi vector< pair< int, int> >
#define all(x) x.begin(), x.end()
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define forn(i,a,n) for(ll i=a;i<n;i++)
#define scan(arr,a,n) for(ll i=(a);i<(n);i++)cin>>(arr)[i];
#define print(arr,a,n) for(ll i=(a);i<(n);i++)cout<<(arr)[i]<<" ";

ll add(ll x, ll y) {ll res = x + y; return (res >= mod ? res - mod : res);}
ll mul(ll x, ll y) {ll res = x * y; return (res >= mod ? res % mod : res);}
ll sub(ll x, ll y) {ll res = x - y; return (res < 0 ? res + mod : res);}
ll power(ll x, ll y) {ll res = 1; x %= mod; while (y) {if (y & 1)res = mul(res, x); y >>= 1; x = mul(x, x);} return res;}
ll mod_inv(ll x) {return power(x, mod - 2);}


int main(){
    fast;
    #ifndef ONLINE_JUDGE
    freopen("input1.txt","r",stdin);
    freopen("output1.txt","w",stdout);
    #endif
    string s;
    cin>>s;
    ll n=s.size();

    
    forn(i, 0, n){
        if(s[i] == '?')s[i]='D';
    }
    cout<<s<<endl;
}

Measured memory_bytes: 3752
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

int32_t N;
int32_t a[100];
std::pair<int, int> res[100];
int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> N;
	for (size_t i = 0; i < N; i++)
	{
		in >> a[i];
	}
	auto ave = std::accumulate(a, a + N, 0);

	for (size_t i = 0; i < N; i++)
	{
		res[i].first = std::abs(a[i] * N - ave);
		res[i].second = i;
	}
	std::sort(res, res + N);
	out << res[0].second << endl;

	return 0;
}
#endif

#if 0
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

int32_t N, K;
uint32_t a[1001];
uint32_t mul[1000100];
int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> N >> K;
	for (int32_t i = 0; i < N; i++)
	{
		in >> a[i+1];
		a[i + 1] += a[i];
	}
	auto iter = mul;
	for (int32_t i = 1; i <= N; i++)
	{
		for (int32_t j = i+1; j <= N+1; j++)
		{
			*iter++ = a[j - 1] - a[i - 1];
		}
	}

	uint32_t mask = 0;
	for (int32_t d = 31; d >= 0; --d)
	{
		uint32_t next = mask | (uint32_t(1) << d);

		int32_t sum = 0;
		for (size_t i = 0; i < (iter - mul); i++)
		{
			if ((mul[i] & next)==next) {
				++sum;
			}
		}

		if (sum >= K) {
			mask = next;
		}
	}
	out << mask << endl;



	return 0;
}
#endif


Measured memory_bytes: 888
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <math.h>
#include <numeric>
#include <cmath>
#include <limits>

using namespace std;
int gcd(long long x, long long y);
int lcm(long long x, long long y);

int main(void){

	int a,b;
	cin >> a >> b;
	cout << a+ b/2 <<endl;

	return 0;
}

int gcd(long long x, long long y)
{
    long long r;

    while((r = x % y) != 0)
    {
        x = y;
        y = r;
    }
    return y;
}

int lcm(long long x, long long y)
{

    return (x * y / gcd(x, y));
}

Measured memory_bytes: 764
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-
import sys
import re
import math
import itertools
import collections
import bisect
#sys.stdin=file('input.txt')
#sys.stdout=file('output.txt','w')
#10**9+7
mod=1000000007
#mod=1777777777
pi=3.1415926535897932
IS=float('inf')
xy=[(1,0),(-1,0),(0,1),(0,-1)]
bs=[(-1,-1),(-1,1),(1,1),(1,-1)]
def niten(a,b): return abs(a-b) if a>=0 and b>=0 else  a+abs(b) if a>=0 else abs(a)+b if b>=0 else abs(abs(a)-abs(b))
def fib(n): return [(seq.append(seq[i-2] + seq[i-1]), seq[i-2])[1] for seq in [[0, 1]] for i in range(2, n)]
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b//gcd(a,b)
def eucl(x1,y1,x2,y2): return ((x1-x2)**2+(y1-y2)**2)**0.5
def choco(xa,ya,xb,yb,xc,yc,xd,yd): return 1 if abs((yb-ya)*(yd-yc)+(xb-xa)*(xd-xc))<1.e-10 else 0
#def pscl(num,l=[1]):
#    for i in range(num):
#        l = map(lambda x,y:x+y,[0]+l,l+[0])
#    return l

# "!/usr/bin/env pypy3
# pscl 要修正

def prime_t(t):
    i=2
    while i**2<=t:
        if t%i==0:
            return 0
        i+=1
    return 1


n=int(input())
a=[int(i) for i in input().split()]
tmp=a[0]
ans=chk=0
for i in range(1,n):
    tmp=lcm(tmp,a[i])
if n%2!=0: tmp=lcm(tmp,a[-1])
y=tmp-1
p=0
for i in a:
   p+=y%i
print(p)

Measured memory_bytes: 3956
# /usr/bin/python
# -*- coding: utf-8 -*-
import sys


n = int(sys.stdin.readline().rstrip())
An = [0] + list(map(int, sys.stdin.readline().rstrip().split())) + [0]
asum = 0
for i in range(1,n+2):
  asum = asum+abs(An[i]-An[i-1])

for i in range(1,n+1):
  ans = asum-abs(An[i]-An[i-1])-abs(An[i+1]-An[i])+abs(An[i+1]-An[i-1])
  print(ans)


Measured memory_bytes: 14048
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <complex>

using namespace std;

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

constexpr int MAXN = 100005;
int n, m;
vector<pii> graph[MAXN];
int in_deg[MAXN];
int uf[MAXN];
int dist[MAXN];

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

    scanf("%d %d", &n, &m);
    int u, v, w;
    for (int i = 0; i < m; ++i) {
        scanf("%d %d %d", &u, &v, &w);
        graph[u].push_back({v, w});
        ++in_deg[v];
    }

    queue<int> q;
    memset(dist, -1, sizeof(dist));
    for (int i = 1; i <= n; ++i) {
        if (in_deg[i] == 0) {
            dist[i] = 0;
            q.push(i);
        }
    }

    bool valid = true;
    while (valid and !q.empty()) {
        int u = q.front();
        q.pop();

        for (const pii& p : graph[u]) {
            int v = p.first;
            int w = p.second;
            if (dist[v] == -1) {
                dist[v] = dist[u] + w;
                q.push(v);
            } else {
                valid &= (dist[v] == dist[u] + w);
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        valid &= dist[i] != -1;
    }

    printf("%s\n", valid ? "Yes" : "No");

    return 0;
}

Measured memory_bytes: 7148
#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>
#include <numeric>
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; }

constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int inf = 1 << 28;
//constexpr long long mod = 1000000007LL;
//constexpr long long mod = 998244353LL;

using namespace std;
typedef unsigned long long ull;
typedef long long ll;


struct SCORE {
	ll ac, pena, id;
	SCORE(ll _ac, ll _pena, ll _id) :ac(_ac), pena(_pena), id(_id) {}
	SCORE() :ac(0), pena(0), id(0) {}
	bool operator<(const SCORE& s) {
		if (ac == s.ac) {
			if (pena == s.pena) return id < s.id;
			else return pena < s.pena;
		}
		else {
			return ac > s.ac;
		}
	}
	bool operator ==(const SCORE& s) {
		return pena == s.pena && ac == s.ac;
	}
};
int main()
{
	/*
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	*/
	int kkt = 89;
	while (kkt) {
		ll T, P, R; scanf("%lld %lld %lld",&T, &P, &R); if (T == 0 && P == 0 && R == 0) break;
		vector<SCORE> score(T); for (int i = 0; i < T; i++) score[i].id = i + 1;
		vector<vector<ll>> miss(T, vector<ll>(P));
		for (int i = 0; i < R; i++) {
			ll m, t, p; scanf("%lld %lld %lld", &t,&p,&m); t--; p--;
			string s; cin >> s;
			int j = 0;
			if (s == "WRONG") j = 1;
			if (j == 0) {
				score[t].ac++;
				score[t].pena += m + miss[t][p];
			}
			else {
				miss[t][p] += 1200;
			}
		}
		sort(score.begin(), score.end());
		for (int i = 0; i < T; i++) {
			cout << score[i].id << " " << score[i].ac << " " << score[i].pena << "\n";
		}
	}
	return 0;

}



Measured memory_bytes: 3248
N = int(input())
l = [1,2,3,4,5,6,7,8,9]

for i in range(N):
  x = l[i]
  if x%10 != 0:
    l.append(x*10 + x%10 -1)
  l.append(x*10 + x%10)  
  if x%10 != 9:
    l.append(x*10 + x%10 +1)
    
print(l[N-1])

Measured memory_bytes: 87952