akhauriyash/Code-Regression huggingface dataset:
x, k, d = map(int, input().split())

if k%2 == 0: #偶数の場合
    flg = 1
else:
    flg = 0
x = abs(x) #対称性から
if 2*x < d:
    if flg: #元の場所
        print(x)
    else:
        print(d-x)
else:
    if x < d: #原点を超える
        if flg:
            print(x)
        else:
            print(d-x)
    else: #原点を超えない値がある
        tmp = x // d #移動した回数
        if tmp >= k:
            print(x-d*k)
        else:
            s = x - d*tmp
            t = abs(s-d)
            if tmp%2 == 0: #偶数
                if flg:
                    print(s)
                else:
                    print(t)
            else:
                if flg:
                    print(t)
                else:
                    print(s)


Measured memory_bytes: 9144
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int maxn = 2*1e5+10;

string s;
ll l,r,len[maxn],cnt[100][maxn],ans[30];
int KMP[maxn];

int pre_calc(string s, int type) {
    memset(KMP,0,sizeof(KMP));
    //cout<<s<<endl;
    int n= s.length();
    for (int i=0;i<n;i++) {
        if (i==0) KMP[i]=-1;
        else {
            KMP[i] = KMP[i-1];
            while (1) {
                //cout<<i<<" "<<KMP[i]<<endl;
                if (s[KMP[i]+1] == s[i]) {
                    KMP[i]++;
                    break;
                }
                if (KMP[i]==-1) break;
                KMP[i] = KMP[KMP[i]];
            }
        }
    }
    //cout<<"fuk"<<endl;
    int tmp = KMP[n-1];
    //cout<<tmp<<endl;
    if (type==1) while (tmp*2+2>=n) tmp=KMP[tmp];
    else while (tmp*2+2>n) tmp=KMP[tmp];
    return tmp+1;
}

void calc(ll LEN,ll coe) {
    int T1 = pre_calc(s,1);
    string s2 = "";
    for (int i=0;i<s.length()-T1;i++) s2+=s[i];
    int T2 = pre_calc(s2,2);
    int sz=0;
    //cout<<T1<<" "<<T2<<endl;
    for (int i=T2;i<s2.length()-T2;i++) {
        len[sz]++;
        cnt[sz][s2[i]-'a']++;
    }
    sz++;
    for (int i=0;i<T2;i++) {
        len[sz]++;
        cnt[sz][s2[i]-'a']++;
    }
    sz++;
    while (len[sz-1]<=LEN) {
        len[sz] = len[sz-1] + len[sz-2];
        for (int i=0;i<26;i++) cnt[sz][i] = cnt[sz-1][i] + cnt[sz-2][i];
        sz++;
        ///cout<<len[sz-1]<<endl;
    }
    for (int i=sz-1;i>=2;i--) {
        if (LEN>=len[i]) {
            LEN-=len[i];
            for (int j=0;j<26;j++) ans[j]+= coe*cnt[i][j];
        }
    }
    for (int i=0;i<LEN;i++) ans[s[i]-'a']+=coe;

}

int main() {
   // freopen("in.txt","r",stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>s;
    cin>>l>>r;
    calc(r,1);
    calc(l-1,-1);
    for (int i=0;i<26;i++) cout<<ans[i]<<" ";
}



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

int main(){

  int n, a, b;
  char c;

  int card[4][13] = {};

  cin >> n;

  for( int i = 0; i < n; i++){
    cin >> c >> b;
    b = b - 1;
    if( c == 'S') a = 0;
    if( c == 'H') a = 1;
    if( c == 'C') a = 2;
    if( c == 'D') a = 3;

    card[a][b] = 1;
  }

  for( int i = 0; i < 4; i++){
    for( int j = 0; j < 13; j++){
      if( card[i][j] != 1) {
	     if( i == 0) {
	       cout << "S" << " " << j + 1 ;
	     } else if( i == 1) {
	       cout << "H" << " " << j + 1 ;
	     } else if( i == 2) {
	       cout << "C" << " " << j + 1;
	     } else {
	       cout << "D" << " " << j + 1;
	     }
      cout << endl;
      }
   }
 }

return 0;
}

Measured memory_bytes: 3080
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0);

ll n,a[100001],m,x,i,b[100001];

int main()
{
	ll l;
	cin>>l;
	double length = l / 3.0; 
  
    // l -= length; 
  
    // finding breadth 
    double breadth = l / 3.0; 
  
    // finding height 
    double height = l /3.0; 
  
    double p= length * breadth * height; 
    printf("%.12lf",p);
} 

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n, inp;
    cin >> n;
    map<ll, ll> mpl;
    for(ll i=1; i<=n; i++){
        cin >> inp;
        mpl[inp] = i;
    }
    for(ll i=1; i<=n;i++)
        cout << mpl[i] << " ";
    return 0;
}

Measured memory_bytes: 7040
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		String X = sc.next();
		String Y = sc.next();
		String ans = " ";

		if ( X.compareTo(Y) < 0 ) {
			ans = "<";
		} else if ( X.compareTo(Y) > 0 ) {
			ans = ">";
		} else {
			ans = "=";
		}

		System.out.println( ans );
	}
}

Measured memory_bytes: 23764
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<climits>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<iomanip>
using namespace std;

#define rep(i,j,n) for(int i=(j);i<(n);i++)
#define erep(i,j,n) for(int i=(j);i<=(n);i++)
#define all(i) i.begin(),i.end()
#define rall(i) i.rbegin(),i.rend()
#define INF 1e9
const int mod = 1e9+7;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef pair<int, int> pi;
typedef long long i64;

int main() {
  int n;
  cin >> n;
  int cou = 1;
  rep(i, 0, n) {
    int a;
    cin >> a;
    if(a % 2 == 0) cou *= 2;
  }
  int ans = pow(3, n) - cou;
  cout << ans << endl;
}


Measured memory_bytes: 256
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
    ll a,b;
}c[100010];
bool cmp(node a ,node b)
{
    return a.a+a.b>b.a+b.b;
}
int main()
{
   int n;
   scanf("%d",&n);
   for(int i=1;i<=n;i++)
    scanf("%lld%lld",&c[i].a,&c[i].b);
   sort(c+1,c+1+n,cmp);
   ll sum1=0,sum2=0;
   for(int i=1;i<=n;i++)
   {
       if(i&1)sum1+=c[i].a;
       else sum2+=c[i].b;
   }
   printf("%lld\n",sum1-sum2);
    return 0;
}


Measured memory_bytes: 1792
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

def gcd(a, b):
	# if a == 0:
	# 	return b
	# elif b == 0:
	# 	return a
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)

Li = [0]*(N+2)
Ri = [0]*(N+2)
A.append(0)
A.insert(0, 0)

for i in range(N+1):
	Li[i+1] = gcd(Li[i], A[i])

for i in range(N, -1, -1):
	Ri[i] = gcd(Ri[i+1], A[i])

# print(Li)
# print(Ri)

M = []
for i in range(1, N+1):
	M.append(gcd(Li[i],Ri[i+1]))
# print(M)
print(max(M))


Measured memory_bytes: 15064
#include <iostream>
#include <string>

using namespace std;

long n,k;
long d[110];
long a[110][110];
bool b[110];

int main() {

  

  cin >> n >> k;
  
  for(int i=0 ; i<k ; i++){
    cin >> d[i];
    for(int j=0 ; j<d[i] ; j++){
      cin >> a[i][j];
      a[i][j]--;
    }
  }

  
  for(int i=0 ; i<n ; i++){
    b[i]=false;
  }


  for(int i=0 ; i<k ; i++){
    for(int j=0 ; j<d[i] ; j++){
      b[a[i][j]]=true;
      
    }
  }


  long long sum = 0;
  for(int i=0 ; i<n ; i++)
    if(!b[i])
      sum++;
  
  cout <<sum << endl;

  
  
  return 0;
}



Measured memory_bytes: 3704
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=int(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
#define rAll(x) (x).rbegin(),(x).rend()
using namespace std;
using ll = long long;

int main(){
    long long H;cin>>H;
    cout<<((1LL<<(63-__builtin_clzll(H)+1))-1)<<endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <cmath>
#include <csignal>
#include <cstdio>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>

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

int main() {
    int h = 0, w = 0;
    cin >> h >> w;
    vector<vector<int>> dis(10, vector<int>(10));
    for (int i=0; i<10; i++) {
        for (int j=0; j<10; j++) {
            cin >> dis.at(i).at(j);
        }
    }
    for (int k=0; k<10; k++) {
        for (int i=0; i<10; i++) {
            for (int j=0; j<10; j++) {
                dis.at(i).at(j) = min(dis.at(i).at(j), dis.at(i).at(k) + dis.at(k).at(j));
            }
        }
    }
    int magic = 0;
    for (int i=0; i<h*w; i++) {
        int tmp = 0;
        cin >> tmp;
        if (tmp == -1) continue;
        magic += dis.at(tmp).at(1);
    }
    cout << magic << endl;
    return 0;
}
 

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>
#include <bitset>
#include <cstdint>

using namespace std;
using lli = long long int;
using i64 = int64_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

i64 n;
string s;

int main() {
  cin >> n >> s;
  vector<i64> c(n + 1);
  for (i64 i = 1; i <= n; ++i) {
    c[i] = (s[i - 1] == '#' ? 1 : 0) + c[i - 1];
  }
  i64 ans = 1e15;
  for (i64 i = 0; i <= n; ++i) {
    i64 b = c[i],
        w = n - i - (c[n] - c[i]);
    ans = min(ans, b + w);
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 2180
N = int(input())
x = [0]* N
y = [0] * N
for i in range(N):
  a , b = map(int,input().split())
  x[i] = a+b
  y[i] = a-b

ans = max([max(x) - min(x),max(y) - min(y)])
print(ans)

Measured memory_bytes: 24712
#include <iostream>
#define ll long long
using namespace std;
int n,m;
char c[410][410];
bool visit[410][410]={0};
ll res=0;
int t,tt;
void dfs(int x,int y)
{
	(c[x][y]=='.' ? t : tt)++;
	visit[x][y]=1;
	if (x>0 && c[x-1][y]!=c[x][y] && !visit[x-1][y]) dfs(x-1,y);
	if (y>0 && c[x][y-1]!=c[x][y] && !visit[x][y-1]) dfs(x,y-1);
	if (x<n-1 && c[x+1][y]!=c[x][y] && !visit[x+1][y]) dfs(x+1,y);
	if (y<m-1 && c[x][y+1]!=c[x][y] && !visit[x][y+1]) dfs(x,y+1);
}
int main()
{
	cin >>n>>m;
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<m;j++)
		{
			cin >>c[i][j];
		}
	}
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<m;j++)
		{
			if (!visit[i][j])
			{
				t=tt=0;
				dfs(i,j);
				res+=(ll)t*tt;
			}
		}
	}
	cout <<res;
	return 0;
}

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

int main() {
	string S;int K; cin >>S>>K;
	char s; long long j = 1LL << 60;
	for(int i = 0 ; i < S.size() ; i++){
		if(S[i] != '1'){
			s = S[i];
			j = i;
			break;
		}
	}
	if(K-1 < j)cout << 1 << endl;
	else cout << s << endl;
}

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

int main(){
  int w,h,n; cin >> w >> h >> n;
  int x1 = 0; int x2 = w;
  int y1 = 0; int y2 = h;
  int x,y,a;
  rep(i,n){
    cin >> x >> y >> a;
    if(a == 1) x1 = max(x1, x);
    else if(a == 2) x2 = min(x2, x);
    else if(a == 3) y1 = max(y1, y);
    else if(a == 4) y2 = min(y2, y);
  }
  cout << max(0, x2-x1)*max(0, y2-y1) << endl;
}

Measured memory_bytes: 256
from bisect import bisect_left,bisect_right
N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

num=[0]*30
for i in range(30):
    t = pow(2,i)
    K=sorted(i%(2*t) for i in A)
    L=sorted(i%(2*t) for i in B)
    #L=sort()
    #print(K,L)
    a = 0
    #尺取り法,i*tより小さい整数を数える
    S=[i*t for i in range(1,5)]
    count=[N]*4
    for k in K:
        for j in range(4):
            while L[count[j]-1]+k>=S[j] and count[j]>0:
                count[j]-=1
        a +=count[3]-count[2]+count[1]-count[0]
        #print(count,a)
    num[i]=a%2
ans =0
s=1
for z in num:
    ans += z*s
    s*=2
print(ans)



Measured memory_bytes: 141572
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics.CodeAnalysis;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp6
{
    class Program
    {
        static void Main(string[] args)
        {
            var a = int.Parse(Console.ReadLine());
            var b = int.Parse(Console.ReadLine());
            var c = int.Parse(Console.ReadLine());
            var d = int.Parse(Console.ReadLine());

            Console.WriteLine(Math.Min(a,b) + Math.Min(c,d));
        }
    }
}


Measured memory_bytes: 11092
#![allow(unused_imports)]

use text_io::*;
use proconio::*;
use std::collections::*;
use std::process::exit;
use std::cmp::*;
use itertools::Itertools;

fn main() {
    input! {
    n:usize,
    d:usize,
    v:[[isize; d]; n],
    }
    let mut ans = 0;
    let mut va = Vec::new();
    for i in 0..2000 {
        va.push(i*i);
    }
    for i in 0..n {
        for j in i+1..n {
            let mut s=0;
            for k in 0..d {
                s+=(v[i][k]-v[j][k])*(v[i][k]-v[j][k]);
            }
            for k in 0..200 {
                if s==va[k] {
                    ans+=1;
                }
            }
        }
    }
    println!("{}",ans);
}

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

int main(){
    // あとで消す
    //std::ifstream in("cin3.txt");
    //std::cin.rdbuf(in.rdbuf());

    int N;
    cin >> N ;

    int prev,next,tmp=0,max=0;
    cin >> prev;

    for(int i=0;i<N-1;i++){
        cin >> next;
        if(prev>=next){
            tmp++;
        }else{
            tmp=0;
        }
        if(tmp>max){
            max=tmp;
        }
        prev = next;
    }

    cout << max << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(int i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(int i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define uniq(x) (x).erase(unique((x).begin(), (x).end()), (x).end())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll n, x, c;
    cin >> n >> x;
    vector<pair<ll, ll>> dp(n + 1);
    ll ans = 0;
    
    rep(i, n + 1) {
        if (i == 0) {
            dp[i] = pair<ll, ll>(1, 1);
        }
        else {
            ll total = dp[i - 1].first * 2 + 3;
            ll patty = dp[i - 1].second * 2 + 1;
            dp[i] = pair<ll, ll>(total, patty);
        }
    }
    
    c = x;
    
    if ((n == 0) && (c == 1)) {
        ans = 1;
    }
    else {
        for(ll i = n; i > 0; i--) {
            if (c > 0) {
                c--;
            }
            
            if (dp[i - 1].first <= c) {
                c -= dp[i - 1].first;
                ans += dp[i - 1].second;
            }
            else {
                continue;
            }
            
            if (c > 0) {
                c--;
                ans++;
            }
            
            if (dp[i - 1].first <= c) {
                c -= dp[i - 1].first;
                ans += dp[i - 1].second;
            }
            else {
                continue;
            }
            
            if (c > 0) {
                c--;
            }
            
            if (c <= 0) {
                break;
            }
        }
        
        if (c > 0) {
            ans++;
        }
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // long long64_t, long long*_t
#include <cstdio> // prlong longf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <iomanip> //setprecision
#include <limits>
using namespace std;
int main(){
  int n,k;
  long long ans;
  cin >> n >> k;
  vector<long long> h(n);
  for(int i=0; i< n; i++) cin >> h[i];
  sort(h.begin(),h.end());
  ans = h[k-1]-h[0];
  for(int i=0; i<=n-k; i++){
    ans=min(h[i+k-1]-h[i],ans);
  }
  cout << ans << endl;
}


Measured memory_bytes: 1152
/**
 *    author:  tourist
 *    created: 09.08.2020 15:48:46       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  const int MAX = 60;
  vector<vector<int>> cnt(MAX, vector<int>(MAX));
  for (int i = 0; i < n; i++) {
    long double x;
    cin >> x;
    long long y = (long long) (x * 1e9 + 0.5);
    int a = 0, b = 0;
    while (y % 2 == 0) {
      y /= 2;
      a += 1;
    }
    while (y % 5 == 0) {
      y /= 5;
      b += 1;
    }
    cnt[a][b] += 1;
  }
  long long ans = 0;
  for (int i = 0; i < MAX; i++) {
    for (int j = 0; j < MAX; j++) {
      for (int ii = 0; ii < MAX; ii++) {
        for (int jj = 0; jj < MAX; jj++) {
          if (make_pair(i, j) <= make_pair(ii, jj)) {
            if (i + ii >= 18 && j + jj >= 18) {
              if (i == ii && j == jj) {
                ans += (long long) cnt[i][j] * (cnt[i][j] - 1) / 2;
              } else {
                ans += (long long) cnt[i][j] * cnt[ii][jj];
              }
            }
          }
        }
      }
    }
  }
  cout << ans << '\n';
  return 0;
}


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

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

using namespace std;

pair<int,int> f(string s){
  if(s[0] == 'n') {
    if (s.size() > 5) {
      auto p = f(s.substr(5));
      return make_pair((p.first - 45) * 2, p.second + 1);
    } else return make_pair(0, 0);
  } else {
    if (s.size() > 4) {
      auto p = f(s.substr(4));
      return make_pair((p.first + 45) * 2, p.second + 1);
    } else return make_pair(90, 0);
  }
}

int main() {
  while(1){
    string s;
    cin>>s;
    if(s=="#")break;
    int m,c;
    tie(c,m) = f(s);
    m = 1 << m;
    while(!(m%2 || c%2)) {m/=2;c/=2;}
    if (m>1)
      cout << c<<'/'<<m<<endl;
    else
      cout<<c<<endl;
  }
  return 0;
}

Measured memory_bytes: 1196
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
    int c,a[20];
}p[20];
int ans[15],v[20];
ll ANS=1e10,sum;
int n,m,u,x;
void dfs(int cnt,int pre){
    if(cnt==u){
        sum=0;
        fill(v,v+20,0);
        for(int j=0;j<cnt;j++){
            for(int k=0;k<m;k++)
                v[k]+=p[ans[j]].a[k];
            sum+=p[ans[j]].c;
        }
        int flag=1;
        for(int j=0;j<m;j++) if(v[j]<x) {flag=0;break;}
        if(flag) ANS=min(ANS,sum);
        return;
    }
    for(int j=0;j<=n;j++){
        if(j>pre){
            pre=j;
            ans[cnt]=pre;
            dfs(cnt+1,pre);
        }
    }
}

int main()
{
    cin>>n>>m>>x;
    for(int i=1;i<=n;i++){
        cin>>p[i].c;
        for(int j=0;j<m;j++)
            cin>>p[i].a[j];
    }
    for(u=1;u<=n;u++){
        dfs(0,0);
    }
    if(ANS==1e10) puts("-1");
    else cout<<ANS;
    return 0;
}

Measured memory_bytes: 3608
#include<stdio.h>
int main()
{
	int i,n,a;
	int max = -1000000;
	int min = 1000000;
	long sum=0;

	scanf("%d",&n);
	for (i = 0; i < n;i++){
		scanf("%d", &a);

		if (max < a) max = a;
		if (min > a)min = a;

		sum += a;
	}
	printf("%d %d %ld\n", min, max, sum);
	return 0;
}

Measured memory_bytes: 600
import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args){
        // input N
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        if (N >= 30){
            System.out.println("Yes");
        }
        else{
            System.out.println("No");
        }
    }
}

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

#define int long long

bool grid[21][21];

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int N;
  while ( cin >> N, N ) {
    fill_n(*grid, 21*21, false);

    for ( int i = 0; i < N; i++ ) {
      int x, y;
      cin >> x >> y;
      grid[y][x] = true;    
    }

    int nx = 10, ny = 10;
    int cnt = 0;
    if ( grid[ny][nx] ) {
      cnt++;
      grid[ny][nx] = false;
    }
    int M;
    cin >> M;
    for ( int i = 0; i < M; i++ ) {
      char c;
      int a;
      cin >> c >> a;
      if ( c == 'N' ) {
	for ( int i = 0; i < a; i++ ) {
	  ny++;
	  if ( grid[ny][nx] ) {
	    cnt++;
	    grid[ny][nx] = false;
	  }
	}
      }
      if ( c == 'E' ) {
	for ( int i = 0; i < a; i++ ) {
	  nx++;
	  if ( grid[ny][nx] ) {
	    cnt++;
	    grid[ny][nx] = false;
	  }
	}
      }
      if ( c == 'S' ) {
	for ( int i = 0; i < a; i++ ) {
	  ny--;
	  if ( grid[ny][nx] ) {
	    cnt++;
	    grid[ny][nx] = false;
	  }
	}
      }
      if ( c == 'W' ) {
	for ( int i = 0; i < a; i++ ) {
	  nx--;
	  if ( grid[ny][nx] ) {
	    cnt++;
	    grid[ny][nx] = false;
	  }
	}
      }
    }

    if ( cnt == N ) cout << "Yes" << endl;
    else cout << "No" << endl;
  }  
  return 0;
}



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

int main(){
    int a,b;
    cin >> a >> b;
    if(a + b == 15){
        cout << "+" << endl;
    }else if(a * b == 15){
        cout << "*" << endl;
    }else{
        cout << "x" << endl;
    }
    return 0;
}



Measured memory_bytes: 3548
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using P = pair<int, int>;
using vec = vector<int>;
using mat = vector<vector<int>>;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define endl "\n"

constexpr int MOD = 998244353;
const int INF = 1 << 30;

lint dp[3100][3100] = {};

int main() {
    int n, s;
    cin >> n >> s;
    vec a(n);
    rep(i, n) cin >> a[i];

    sort(all(a));

    dp[0][0] = 1;

    rep(i, n) {
        int ni = i+1;
        for (int j = 0; j <= s; j++) {
            dp[ni][j] += (dp[i][j] * 2) % MOD;
        }
        for (int j = 0; j + a[i] <= s; j++) {
            dp[ni][j + a[i]] += dp[i][j];
            dp[ni][j + a[i]] %= MOD;
        }
    }
    cout << dp[n][s] << endl;
    return 0;
}

Measured memory_bytes: 76220
#pragma region header
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <math.h>
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rev(i, n) for(int i = (int)(n - 1); i >= 0; i--)
#define rev1(i, n) for(int i = (int)(n); i > 0; i--)
#define pb push_back
#define ts to_string
#define all(v) (v).begin(), (v).end()
#define vi vector<int>
#define vvi vector<vector<int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vs vector <string>
#define vvs vector <vector<string>>
#define pq  priority_queue<int>
using ll = long long;
/* ----------------よく使う数字や配列----------------- */
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
constexpr ll mod = 1e9 + 7;
constexpr long double pi = 3.141592653589793238462643383279;
/* ----------------------end----------------------- */
/* --------------------ライブラリ-------------------- */
ll fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i % mod;
}
ll gcd(ll a, ll b) {        //最大公約数
    if (b == 0) return a;
    return gcd(b, a % b);
}
ll lcm(ll a, ll b) {      //最小公倍数
    return a * b / gcd(a, b);
}
bool isprime(ll a)//素数判定、primeならtrue,違うならfalse
{
    if (a < 2) return false;
    else if (a == 2) return true;
    else if (a % 2 == 0) return false;
    double m = sqrt(a);
    for (int i = 3; i <= m; i += 2)
    {
        if (a % i == 0)
        {
            return false;
        }
    }
    // 素数である
    return true;
}
ll ketasum(ll n) {    //各桁の和
    ll sum = 0;
    while (n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
ll kind(vi SYURUI) {//vector<int>型の配列の要素の種類数
    int size = SYURUI.size();
    sort(all(SYURUI));
    int cnt = 1;
    rep(i, size-1) {
        if (SYURUI[i] != SYURUI[i + 1])cnt++;
    }
    return cnt;
}
/* ----------------------end----------------------- */
#pragma endregion
signed main() {
    int A, B, C, D; cin >> A >> B >> C >> D;
    cout << max({ A * C,A * D,B * C,B * D }) << endl;
}








Measured memory_bytes: 3680
#include <bits/stdc++.h>
    #define rep(i,n) for(int i = 0; i < (n); i++)
     
    using namespace std; 
    using ll = long long;
    using P = pair<int,int>; 
    
    int main() {
     int n,m;
     cin >> n >> m;
     
    cout << n*(n-1)/2 + m*(m-1)/2 << '\n';
    
     return 0;
    }
    

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<Int> a(n);
  for(Int i=0;i<n;i++) cin>>a[i];
  Int q;
  cin>>q;
  for(Int i=0;i<q;i++){
    Int b,e,t;
    cin>>b>>e>>t;
    swap_ranges(a.begin()+b,a.begin()+e,a.begin()+t);
  }
  for(Int j=0;j<n;j++){
    if(j) cout<<" ";
    cout<<a[j];
  }
  cout<<endl;
  return 0;
}



Measured memory_bytes: 3072
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll a[200010],ans=0;
bool cmp(ll x,ll y) {
	return x>y;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
	sort(a+1,a+n+1,cmp);
	queue<ll> q;
	q.push(a[1]);
	for(int i=2;i<=n;++i) {
		ans+=q.front();q.pop();
		q.push(a[i]);
		q.push(a[i]);
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 6832
#include <bits/stdc++.h>
using namespace std;
typedef long long int LL;
typedef pair<int,int> P;
typedef pair<LL,int> LP;
typedef pair<LL, LL> LLP;
const int INF=1<<30;
const LL MAX=1e9+7;
LL N;
vector<LL> D, d;
int main() {
  int i, j, k;
  
  cin >> N;

  D.resize(N+1);
  d.assign(N+1, 0);
  for (i = 0; i < N; ++i) {
    cin >> D[i];
    d[D[i]]++;
  }

  LL ans = 1;
  for (i = 1; i < N; ++i) {
    if (d[i+1] == 0) continue;
    for (j = 0; j < d[i+1]; ++j) {
      ans *= d[i];
      ans %= 998244353;
    }
  }

  if (D[0] != 0) {
    ans = 0;
  }

  for (i = 1; i < N; ++i) {
    if (D[i] == 0) ans = 0;
  }

  cout << ans << endl;
}


Measured memory_bytes: 1792
#include <stdio.h>
#include <stdlib.h>
#define MAX 101
#define rep(i,n) for(int i=0;i<n;i++)
#define infinity 1e9
typedef struct tuple{
    int a;
    int b;
    int w;
}tuple;
int n,t=0,cost=0;
int G[MAX][MAX],tags[MAX];
tuple v[5010];
int cmpAscW(const void * n1, const void * n2){
    if (((tuple *)n1)->w > ((tuple *)n2)->w)return 1;
	else if (((tuple *)n1)->w < ((tuple *)n2)->w)return -1;
	else return 0;
}
int min(int x,int y){
    if(x < y)return x;
    else return y;
}
int max(int x,int y){
    if(x<y)return y;
    else return x;
}
void Kruskal(){
    int m,temp=0;
    rep(i,t){
        if(tags[v[i].a] != tags[v[i].b]){
            temp = max(tags[v[i].a],tags[v[i].b]);
            m = min(tags[v[i].a],tags[v[i].b]);
            tags[v[i].a] = m;
            tags[v[i].b] = m;
            cost += v[i].w;
            for(int j=m;j<n;j++){
                if(tags[j] == temp)tags[j]=m;
            }
        }
    }
}
int main(){
    scanf("%d",&n);
    rep(i,5010){
        v[i].w = infinity;
    }
    rep(i,n){
        tags[i] = i;
        rep(j,n){
            scanf("%d",&G[i][j]);
            if(i<j){
                if(G[i][j] != -1){
                    v[t].a = i;
                    v[t].b = j;
                    v[t].w = G[i][j];
                    t++;
                }
            }
        }
    }
    qsort(v, t, sizeof(tuple), cmpAscW);
    Kruskal();
    printf("%d\n",cost);
    return 0;
}


Measured memory_bytes: 2044
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, s, n) for (int i = (s); i < (n); i++)
#define RFOR(i, s, n) for (int i = (n) - 1; i >= (s); i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
#define ALL(a) a.begin(), a.end()
const long long MOD = 1e9+7, INF = 1e18;
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;}



signed main(){
	int K,X;
	cin>>K>>X;
	FOR(i,X-(K-1),X+K){
		if(i!=X-(K-1))cout<<" ";
		cout<<i;
	}
	cout<<endl;
}

Measured memory_bytes: 256
n = input()
list_h = raw_input().split()
h = [int(s) for s in list_h]
count = 1
max_h = h[0]

for i in range(1, n):
 if h[i] >= h[i-1] and h[i] >= max_h:
  count += 1
  max_h = h[i]
print count

Measured memory_bytes: 2696
#include <iostream>
#include <string>
#include <vector>
int main() {
    int n, q;
    std::cin >> n >> q;
    std::string s;
    std::cin >> s;
    std::vector<int> a;
    int x = 0;
    a.push_back(0);
    for (int i = 1; i < n; i++) {
        if (s[i - 1] == 'A' && s[i] == 'C') {
            x++;
        }
        a.push_back(x);
    }
    for (int i = 0; i < q; i++) {
        int l, r;
        std::cin >> l >> r;
        std::cout << (a[r - 1] - a[l - 1]) << std::endl;
    }
}

Measured memory_bytes: 1528
N = int(input())
A = tuple(map(int, input().split()))
M = [-1] * N
acc = 0
for i in range(1, N, 2):
    acc += A[i]
acc *= 2
M[0] = sum(A) - acc
for i in range(N-1):
    M[i+1] = 2*A[i] - M[i]
print(*M)

Measured memory_bytes: 92168
from collections import Counter

n = int(input())
A = [int(i) for i in input().split()]
A = Counter(A)
rec = []
squ = []
for i in A.items():
    if i[1] >= 2:
        rec.append(i[0])
    if i[1] >= 4:
        squ.append(i[0])
rec.sort(reverse=True)
squ.sort(reverse=True)
if len(rec) >= 2 and len(squ) >= 1: 
    print(max(rec[0]*rec[1],squ[0]**2))
elif len(rec) >= 2:
    print(rec[0]*rec[1])
else:
    print(0)

Measured memory_bytes: 18592
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include <fstream>
#include <time.h>
#include <iterator>
#include<random>



#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define m0(x) memset(x,0,sizeof(x))
#define print(x) cout<<x<<endl;
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n);
#define ub(v,n) upper_bound(v.begin(), v.end(), n);
#define int long long
#define all(x) (x).begin(), (x).end()
using namespace std;

int MOD = (ll)1000000000 + 7;
const ll INF = 1e17;
const double pi = acos(-1);
const double EPS = 1e-10;
typedef pair<int, int>P;
const int MAX = 500050;


int N, A, B;
vector<int>v[300030];
set<int>st;
map<int, int>mp;
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	bool debug = 0;
	cin >> N >> A >> B;
	if (N<(A + B - 1) || N>A*B) {
		print(-1); return 0;
	}
	//ーーー構築ーーー
	REP(i, A) {
		v[0].pb(i + A * B - A + 1);
	}
	FOR(i, 1, B) {
		v[i].pb(A*B - A * i - A + 1);
	}
	int nw = A + B - 1;
	int rem = N - nw;
	FOR(i, 1, B) {
		FOR(j, 1, A) {
			if (rem == 0)goto END;
			v[i].pb(A*B - A * i - A + 1 + j);
			rem--;
		}
	}
END:;
	//ーーー構築ーーー

	if (debug) {
		REP(i, B) {
			REP(j, v[i].size()) {
				pe(v[i][j]);
			}cout << endl;
		}
		cout << endl;
	}

	//ーーー座圧ーーー
	REP(i, B) {
		REP(j, v[i].size()) {
			st.insert(v[i][j]);
		}
	}
	int c = 1;
	for (auto x : st) {
		mp[x] = c;
		c++;
	}
	//ーーー座圧ーーー

	REP(i, B) {
		REP(j, v[i].size()) {
			pe(mp[v[i][j]]);
		}
		//cout << endl;
	}
	cout << endl;
}

Measured memory_bytes: 47856
import java.io._
import java.util.StringTokenizer
import scala.util.control.Breaks.{breakable,break}

object Main extends App {
  val in = new InputReader(System.in)
  val pw = new PrintWriter(System.out)

  val MOD = 1e9.toInt + 7

  // 素数modulo `p` の世界での割り算
  // a / b
  def modDiv(a: Int, b: Int, p: Int): Long = {

    // (x ^ n) % p
    def repeatSquares(x: Long, n: Int): Long = {
      if(n == 0)
        1
      else if(n % 2 == 0)
        repeatSquares(x*x % p, n/2)
      else
        (x * repeatSquares(x*x % p, n/2)) % p
    }

    val numer = a % p
    val denom = repeatSquares(b, p-2)

    (numer * denom) % p
  }

  val N = in.next().toInt
  val X = in.next().toInt
  val _S = new Array[Int](N)

  for (i <- 0 until N)
    _S(i) = in.next().toInt


  //
  val S = 0 +: _S.sorted.reverse
  val dp = Array.ofDim[Long](N+1, X+1)
  for (n <- 0 to N; x <- 0 to X)
    dp(n)(x) = -1L

  def calc(i: Int, X: Int): Long = {
    if(i == N)
      X % S(i)
    else if(dp(i)(X) != -1L)
      dp(i)(X)
    else {
      val r1 = (modDiv(1, N+1-i, MOD) * calc(i+1, X % S(i))) % MOD
      val r2 = (modDiv(N-i, N+1-i, MOD)) * calc(i+1, X) % MOD
      dp(i)(X) = (r1 + r2) % MOD
      dp(i)(X)      
    }
  }

  def fact(n: Long, acc: Long): Long =
    if(n == 1)
      acc
    else
      fact(n-1, (n*acc) % MOD)

  val expected = calc(1, X) % MOD
  val ans = expected * fact(N, 1L)
  println(ans % MOD)
}


class InputReader(stream: InputStream) {
  private val reader = new BufferedReader(new InputStreamReader(stream))
  private var tokenizer: StringTokenizer = new StringTokenizer(reader.readLine())
  def next(): String = {
    while (!tokenizer.hasMoreTokens()) {
      tokenizer = new StringTokenizer(reader.readLine())
    }
    tokenizer.nextToken()
  }
}



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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int d,g; cin>>d>>g;
	vector<int>p(d),c(d);
	for(int i=0;i<d;++i)cin>>p.at(i)>>c.at(i);
	int ans=1e9;
	for(int i=0;i<(1<<d);++i){
		vector<int>tp(p);
		int score=0,cnt=0;
		for(int j=0;j<d;++j){
			if(i&(1<<j)){
				score+=(j+1)*100*tp.at(j)+c.at(j);
				cnt+=tp.at(j);
				tp.at(j)=0;
			}
		}
		int k=d-1;
		while(k>=0&&tp.at(k)==0)--k;
		while(k>=0&&tp.at(k)>0&&score<g){
			score+=(k+1)*100;
			--tp.at(k);
			++cnt;
		}
		if(score>=g)ans=min(ans,cnt);
	}
	cout<<ans<<"\n"s;
}


Measured memory_bytes: 3584
object Main extends App{
  import scala.io.StdIn.readLine
  
  val nab = readLine.split(" ").map(_.toLong)
  val n = nab(0)
  val b = nab(1)
  val r = nab(2)
  
  println( ( (n/(r+b))*b + Set( b,math.abs(n%(r+b)) ).min ).toString )
}


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

using namespace std;

int main() {
   ios_base::sync_with_stdio(false);
   int A, B;
   cin >> A >> B;
   if (A <= B) {
      cout << "Impossible\n";
      return 0;
   }
   int N = A + B;
   vector<int> st;
   for (int i = 0; i < N; ++i) {
      if (st.empty()) {
         st.emplace_back(i);
      } else {
         cout << "? " << i << " " << st.back() << endl;
         char ans;
         cin >> ans;
         if (ans == 'N') {
            st.pop_back();
         } else {
            st.emplace_back(i);
         }
      }
   }
   int z = st[0];
   string S;
   for (int i = 0; i < N; ++i) {
      cout << "? " << z << " " << i << endl;
      char ans;
      cin >> ans;
      if (ans == 'Y') {
         S += '1';
      } else {
         S += '0';
      }
   }
   cout << "! " << S << endl;
   return 0;
}


Measured memory_bytes: 852
def search(l,x):
    min_ = 0
    max_ = len(l) - 1
    k = int((min_+max_)/2)
    while(abs(min_-max_) > 1):
        if l[k] > x:
            max_ = k
        elif l[k] < x:
            min_ = k
        else:
            max_ = k
            min_ = k
            break

        k = int((min_+max_)/2)

    if l[max_] == x:
        return max_
    return min_


#print(search([1,5,6,8,12,17,100,101,150],101))
N,M = (int(i) for i in input().split())  

kens = []
ps = [0] * M
ys = [0] * M
for _ in range(N):
    kens.append([])
for i in range(M):
    p,y = (int(i) for i in input().split())
    ps[i] = p
    ys[i] = y
    kens[p-1].append(y)

#print(len(kens))
kens_s = [0] * N
for i in range(N):
    kens_s[i] = sorted(kens[i])

for i in range(M):
    #print(ps[i]-1)
    num = search(kens_s[ps[i]-1],ys[i]) + 1
    print('{0:06d}'.format(ps[i]) + '{0:06d}'.format(num))

Measured memory_bytes: 83104
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int solve(int n,int m){
    vector<int>v1;
    for(int i = 0;i < n;i++){
        int g;
        cin >> g;
        v1.push_back(g);
    }
    vector<int>v2;
    for(int i = 0;i < m;i++){
        int g;
        cin >> g;
        v2.push_back(g);
    }
    copy(v2.begin(),v2.end(),back_inserter(v1));
    sort(v1.begin(),v1.end());
    int max = v1[0];
    for(int i = 1;i < n+m;i++){
        if(max < v1[i] - v1[i - 1]){
            max = v1[i] - v1[i - 1];
        }
    }
    return max;
}
int main(){
    vector<int>a;
    while(1){
        int n ,m;
        cin >> n >> m;
        if(n == m && n == 0)break;
        
        a.push_back(solve(n,m));
    }
    for(int i = 0;i < a.size();i++){
        cout << a[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 3188
#include<bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vector<int> >
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
using ll = long long;
using ld =long double;
//#define int ll
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
#define MAX 9999999
using namespace std;
typedef pair<int, int> pii;
typedef pair<int,pii> piii;
signed main(){
    string s; cin>>s;
    int n=(int)s.size();
    int beg=0,lst=n-1;
    int ans=0;
    while(true){
        
        if(beg==lst||beg>lst)break;
        if(s[beg]=='x'&&s[beg]!=s[lst]){
            ans++;
            beg++;
        }else if(s[lst]=='x'&&s[beg]!=s[lst]){
            ans++;
            lst--;
        }else if(s[beg]==s[lst]){
            beg++;
            lst--;
        }else if(s[beg]!=s[lst]){
            return puts("-1")*0;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

const long long INF = 1LL << 60;

// 入力
int N;
long long h[110000];

// DP テーブル
long long dp[110000];

int main() {
    int N, K; cin >> N >> K;
    for (int i = 0; i < N; ++i) cin >> h[i];

    for (int i = 0; i < 110000; ++i) dp[i] = INF;

    dp[0] = 0;

    for (int i = 0; i < N; ++i) {
        for (int j = 1; j <= K; ++j) {
            chmin(dp[i + j], dp[i] + abs(h[i] - h[i + j]));
        }
    }

    cout << dp[N-1] << endl;
}

Measured memory_bytes: 1920
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			int a = sc.nextInt();
			String op = sc.next();
			int b = sc.nextInt();
			if(op.equals("+"))	System.out.printf("%d\n", a + b);
			else if(op.equals("-"))	System.out.printf("%d\n", a - b);
			else if(op.equals("*"))	System.out.printf("%d\n", a * b);
			else if(op.equals("/"))	System.out.printf("%d\n", a / b);
			else break;
		}
	}
}



Measured memory_bytes: 26368
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define EPS (1e-9)
#define INF (1e17)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
//long long INF=(long long)1E17;
#define i_7 (long long)(1e9+7)
//#define i_7 998'244'353
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
long long po(long a, long b){
    if(b==0){
        return 1;
    }
    
    long long z = po(a,b/2);
    z = mod(z*z);
    if(b%2!=0){
        z = mod(a*z);
    }
    return z;
}
 
bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=std::sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}
 
long long gcd_(long long a, long long b){
  if(a<b){
    std::swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}
 
using namespace std;
//using namespace boost::multiprecision;
//using namespace __gnu_pbds;

long long calc(vector<pair<int, long long>> p){
  int n = p.size();
  REP(i, n) p[i].first = min(p[i].first, n);
  vector<vector<long long>> table(n + 1);
  REP(i, n) table[p[i].first].push_back(p[i].second);
  long long res = 0;
  priority_queue<long long> q;
  for(int d = n; d >= 1; d--){
    for(long long v: table[d]) q.push(v);
    if(q.empty()) continue;
    long long v = q.top();
    q.pop();
    res += v;
  }
  return res;
}
void solve(int n, vector<int> k, vector<long long> l, vector<long long> r){
  vector<pair<int, long long>> pl, pr;
  long long ans = 0;
  REP(i, n){
    if(l[i] >= r[i]){
      ans += r[i];
      pl.push_back(make_pair(k[i], l[i] - r[i]));
    }else{
      ans += l[i];
      pr.push_back(make_pair(n - k[i], r[i] - l[i]));
    }
  }
  ans += calc(pl);
  ans += calc(pr);
  cout << ans << endl;
  return;
}
      
int main(){
  using namespace std;
  int t;
  cin>>t;
  REP(_, t){
    int n;
    cin>>n;
    vector<int> k(n);
    vector<long long> l(n), r(n);
    REP(i, n) cin>>k[i]>>l[i]>>r[i];
    solve(n, k, l, r);
  }
  return 0;
}


Measured memory_bytes: 21504
#include <cstdio>
#include <cstdlib>
#include <math.h>
#include <algorithm>
using namespace std;

int m,nmin,nmax,ten[205],gap,ans;

int main(){
while(1){
	
	
	scanf("%d %d %d",&m,&nmin,&nmax);
	if(m + nmin + nmax == 0)break;
	for(int i = 0;i < m;i++){
		scanf("%d",&ten[i]);
	}
	gap = -1;
	for(int i = nmin - 1;i < nmax ;i++){
		if(ten[i] - ten[i+1] >= gap){
			ans = i + 1;
			gap = ten[i] - ten[i+1];
		}
	}
	
	printf("%d\n",ans);
	
}

return 0;

} 
	
	
	


Measured memory_bytes: 2680
#include <map>
#include <set>
#include <ctime>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cctype>
#include <string>
#include <numeric>
#include <cstring>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std ;
#define rep(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define per(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define loop(s, v, it) for (s::iterator it = v.begin(); it != v.end(); it++)
#define cont(i, x) for (int i = head[x]; i; i = e[i].nxt)
#define clr(a) memset(a, 0, sizeof(a))
#define ass(a, sum) memset(a, sum, sizeof(a))
#define lowbit(x) (x & -x)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define iv inline void
#define enter cout << endl
#define siz(x) ((int)x.size())
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair <int, int> pii ;
typedef vector <int> vi ;
typedef vector <pii> vii ;
typedef set <int> si ;
typedef map <int, int> mii ;
typedef map <string, int> msi ;
const int N = 200010 ;
const int INF = 0x3f3f3f3f ;
const int iinf = 1 << 30 ;
const ll linf = 2e18 ;
const int MOD = 1000000007 ;
void print(int x) { cout << x << endl ; exit(0) ; }
void PRINT(string x) { cout << x << endl ; exit(0) ; }
void douout(double x){ printf("%lf\n", x + 0.0000000001) ; }

int n, m ;
vii p[N] ;
ll tr[N << 2], tag[N << 2] ;

void modify(int v, int s, int t, int l, int r, ll x) {
	if (s >= l && t <= r) {
		tr[v] += x ;
		tag[v] += x ;
		return ;
	}
	int mid = (s + t) >> 1 ;
	if (l <= mid) modify(v << 1, s, mid, l, r, x) ;
	if (r > mid) modify(v << 1 | 1, mid + 1, t, l, r, x) ;
	tr[v] = max(tr[v << 1], tr[v << 1 | 1]) + tag[v] ;
}

signed main(){
	scanf("%d%d", &n, &m) ;
	rep(i, 1, m) {
		int l, r, c ; scanf("%d%d%d", &l, &r, &c) ;
		p[r].pb(mp(l, c)) ;
 	}
	rep(i, 1, n) {
		modify(1, 1, n, i, i, tr[1]) ;
		rep(j, 0, siz(p[i]) - 1) {
			pii q = p[i][j] ;
			modify(1, 1, n, q.fi, i, q.se) ;
		}
	}
	printf("%lld\n", max(tr[1], 0ll)) ;

	return 0 ;
}

/*
写代码时请注意：
	1.ll？数组大小，边界？数据范围？
	2.精度？
	3.特判？
	4.至少做一些
思考提醒：
	1.最大值最小->二分？
	2.可以贪心么？不行dp可以么
	3.可以优化么
	4.维护区间用什么数据结构？
	5.统计方案是用dp？模了么？
	6.逆向思维？
*/


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

    

int main(){
  ll N,K,R,S,P,ans=0;
  string T;
  cin >> N >> K >> R >> S >> P >> T;
  rep(i,K){
    ll j=0;
    while(i+j*K<N){
      if(T.at(i+j*K)=='r'){
        ans+=P;
      }else if(T.at(i+j*K)=='s'){
        ans+=R;
      }else{
        ans+=S;
      }
      if(i+(j+1)*K<N){
        if(T.at(i+j*K)==T.at(i+(j+1)*K)){
          j++;
        }
      }
      j++;
    }
  }
  cout << ans << endl;
         
        
    
  
}


Measured memory_bytes: 512
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int N=300000;
struct node
{
	ll d1,d2;
};
int n,i,j,k,ch[N][2],w[N][2];
ll lt,rt,mid;
vector<node> vct[N];
bool cmp(node a,node b)
{
	return a.d1<b.d1;
}
bool cmq(node a,node b)
{
	return a.d2<b.d2;
}
void dfs(int x)
{
	vct[x].clear();
	if(!ch[x][0]&&!ch[x][1])
	{
		vct[x].push_back((node){0,0});
		return;
	}
	dfs(ch[x][0]);
	dfs(ch[x][1]);
	if(vct[ch[x][0]].size()>vct[ch[x][1]].size())
	{
		swap(ch[x][0],ch[x][1]);
		swap(w[x][0],w[x][1]);
	}
	sort(vct[ch[x][0]].begin(),vct[ch[x][0]].end(),cmq);
	sort(vct[ch[x][1]].begin(),vct[ch[x][1]].end(),cmp);
	ll g=1ll<<60;
	for(int i=vct[ch[x][0]].size()-1,j=0;i>=0;--i)
	{
		while(j<vct[ch[x][1]].size()&&vct[ch[x][0]][i].d2+vct[ch[x][1]][j].d1+w[x][0]+w[x][1]<=mid)
		{
			g=min(g,vct[ch[x][1]][j].d2);
			++j;
		}
		if(g<(1ll<<60))
			vct[x].push_back((node){vct[ch[x][0]][i].d1+w[x][0],g+w[x][1]});
	}
	sort(vct[ch[x][0]].begin(),vct[ch[x][0]].end(),cmp);
	sort(vct[ch[x][1]].begin(),vct[ch[x][1]].end(),cmq);
	g=1ll<<60;
	for(int i=vct[ch[x][0]].size()-1,j=0;i>=0;--i)
	{
		while(j<vct[ch[x][1]].size()&&vct[ch[x][0]][i].d1+vct[ch[x][1]][j].d2+w[x][0]+w[x][1]<=mid)
		{
			g=min(g,vct[ch[x][1]][j].d1);
			++j;
		}
		if(g<(1ll<<60))
			vct[x].push_back((node){g+w[x][1],vct[ch[x][0]][i].d2+w[x][0]});
	}
}
int main()
{
	scanf("%d",&n);
	for(i=2;i<=n;++i)
	{
		scanf("%d%d",&j,&k);
		if(!ch[j][0])
		{
			ch[j][0]=i;
			w[j][0]=k;
		}
		else
		{
			ch[j][1]=i;
			w[j][1]=k;
		}
	}
	lt=0,rt=n*131072ll;
	while(lt<rt)
	{
		mid=lt+rt>>1;
		dfs(1);
		if(vct[1].empty())
			lt=mid+1;
		else
			rt=mid;
	}
	printf("%lld",lt);
	return 0;
}


Measured memory_bytes: 30712