akhauriyash/Code-Regression huggingface dataset:
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)
#define VL vector<ll>
#define VS vector<string>
#define VB vector<bool>
#define VP vector<pair<ll,ll>>
#define VVL vector<vector<ll>>
#define VVP vector<vector<pair<ll,ll>>>
#define PL pair<ll,ll>
#define ALL(v) (v).begin(), (v).end()
ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main() {
    ll n, k;
    cin >> n >> k;
    VL a(n);
    rep(i,0,n) cin >> a[i];
    ll c_front = 0, c_back = 0;
    rep(i,0,n){
        rep(j,i+1,n){
            if(a[i] > a[j]){
                c_front++;
            }else if(a[i] < a[j]){
                c_back++;
            }
        }
    }
    //naibu 
    k = k % MOD;
    ll ans = c_front * k;
    //gaibu kC2 
    ll kk = (k * (k - 1) / 2) % MOD;
    ans += (c_front + c_back) * kk; //c_backが2ブロック間で発生する数 //c_frontが外部ブロック内で発生する数
    ans = ans % MOD;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstring>

#include <iostream>
#include <algorithm>
#include <vector>

#define MAX_N 100000
#define INF   100010

int n;
int fennec, snuke;
int cost_from_1[MAX_N], cost_from_n[MAX_N];
std::vector<int> edge[MAX_N];
std::string      s;

void dfs(int s, int p, int cost[], int d) {
    cost[s] = d;
    std::vector<int>::iterator itr = edge[s].begin();
    while (itr != edge[s].end()) {
        if (*itr != p) dfs(*itr, s, cost, 1+d);
        ++itr;
    }
}

void shortest_path(int source, int cost[]) {
    std::fill(cost, cost+n, INF);
    dfs(source, -1, cost, 0);
}

int main() {
    std::cin >> n;
    for (int i=1; i<n; ++i) {
        int a, b;
        std::cin >> a >> b;
        --a; --b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    shortest_path(  0, cost_from_1);
    shortest_path(n-1, cost_from_n);
    for (int i=0; i<n; ++i) {
        if (cost_from_1[i] <= cost_from_n[i]) ++fennec;
        else                                  ++snuke;
    }
    s = (fennec > snuke) ? "Fennec" : "Snuke";
    std::cout << s << std::endl;
    return 0;
}

Measured memory_bytes: 12800
n = gets.to_i
a = gets.split.map(&:to_i)
h = Hash.new 0
a.each{|x|
  idx = x % 4 == 0 ? 4 : x % 2 == 0 ? 2 : 0
  h[idx] += 1
}

res = h[2] > 0 ? h[0] <= h[4] : h[0] <= h[4] + 1
puts res ? :Yes : :No

Measured memory_bytes: 8452
#include <bits/stdc++.h>
 #define f first
 #define s second
 #define endl '\n'
 #define LL long long
 #define pb push_back
 #define sz(a) (int)a.size()
 #define all(a) a.begin(),a.end()
 #define rall(a) a.rbegin(),a.rend()
 #define debug(x) cerr << #x << " is " << x << endl;
 using namespace std;
 int const MAXN = 2e6 + 9;
 int main(){
    ios_base::sync_with_stdio (0),cin.tie(0);
    int a, b;
    cin >> a >> b;
    cout << 6 - a - b;
 }


Measured memory_bytes: 256
n = int(input())
P = [int(x) for x in input().split()]
cnt = 0
for i in range(1, n - 1):
  if P[i - 1] < P[i] and P[i + 1] < P[i]:
    continue
  if P[i] < P[i - 1] and P[i] < P[i + 1]:
    continue
  cnt += 1
print(cnt)

Measured memory_bytes: 3064
//
//  main.cpp

#include <iostream>
#include <limits.h>
using namespace std;
using ll = long long;
const ll MIN = -(LONG_LONG_MAX-1);

int main(){	
	int N,Q;
	ll T;
	cin >> N >> T >> Q;
	
	ll people[1001];
	ll A[100001];
	int D[100001];
	for(int i=0;i<N;i++){
		cin >> A[i] >> D[i];
	}
	for(int i=0;i<Q;i++){
		cin >> people[i];
		people[i]--;
	}
	
	ll east = MIN;
	ll west = MIN;
	ll t;
	for(int i=0;i<Q;i++){
		if(D[people[i]] == 1){
			east = A[people[i]];
			for(ll j=people[i]+1;j<N;j++){
				if(D[j] == 1){
					east = A[j];
				}else{
					t = (east + A[j])/2;
					break;
				}
			}
			if(T < abs(t - A[people[i]])){
				cout << A[people[i]] + T << endl;
			}else{
				cout << t << endl;
			}
		}else{
			west = A[people[i]];
			for(ll j=people[i]-1;j>=0;j--){
				if(D[j] == 1){
					t = (west + A[j])/2;
					break;
				}else{
					west = A[j];
				}
			}
			if(T < abs(A[people[i]] - t)){
				cout << A[people[i]] - T << endl;
			}else{
				cout << t << endl;
			}
//			cout << min(T - (t - A[people[i]]),t - A[people[i]]) << endl;;
		}
	}
	
	/*
	ll answer[100001]={};
	ll lasteast = MIN;
	ll laststate = MIN;
	for(int i=0;i<N;i++){
		if(D[i] == 1){
			if(lasteast == MIN && laststate == MIN){
				answer[i] = A[i] - T;
			}else if(lasteast != MIN && laststate == MIN){
				if(T < abs(abs(lasteast) - abs(A[i]))/2){
					answer[i] = A[i] - T;
				}else{
					answer[i] = (A[i]+lasteast)/2;
				}
			}
		}else{
			
		}
		
	}*/
	
	return 0;
}

Measured memory_bytes: 4236
import collections
S = list(input())
T = list(input())
counterS = collections.Counter(S)
counterT = collections.Counter(T)
Scou = list(counterS.values())
Tcou = list(counterT.values())
Scou.sort()
Tcou.sort()
if Scou == Tcou:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 12472
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

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; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }

typedef long long  ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
    int n,m,c;
    int b[30];
    int a[30][30];
    cin>>n>>m>>c;
    for(int i=0;i<m;i++){
        cin>>b[i];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>a[i][j];
        }
    }
    int cnt=0;
    for(int i=0;i<n;i++){
        int sum=0;
        for(int j=0;j<m;j++){
            sum+=a[i][j]*b[j];

        }
        if(sum>-c){
            cnt++;
        }
    }
    cout<<cnt<<endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;


public class Main{

	public static void main(String args[]){

		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		char c[] = s.toCharArray();
		
		c[3] = '8';
		
		String st = new String(c);
		System.out.println(st);
	}
}

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

#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define endl "\n"
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define rev(a) (a).rbegin(),(a).rend()
#define pll pair<ll,ll>
#define rep(i,a,b) for(long long i = (a); i <= (b); i++)

const int mod = 1e9+7;
const int N = 1e5+5; 

int main(){
	fast;
	ll t = 1; 
	//cin >> t;
	while(t--){
	    string s; cin >> s;
	    ll len = s.size();
	    cout << s;
	    if(s[len-1] == 's') cout << "es\n";
	    else cout << "s\n";
	}
}

Measured memory_bytes: 3636
#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> // int64_t, int*_t
#include <cstdio> // printf
#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
using namespace std;
typedef long long ll;

int main(int argc, char *argv[])
{
  ll n;
  string s;
  cin >> n;
  cin >> s;

  if (n % 2 != 0) {
    cout << "No";
    return 0;
  }

  auto str1 = s.substr(0, n / 2);

  if (str1 + str1 == s) {
    cout << "Yes";
  } else {
    cout << "No";
  }
}


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

using namespace std;

int dist(int p,vector<int> &x)
{
    int ret = 0;
    for (int i = 0; i < (int)x.size(); ++i) {
        ret += abs(x[i]-p)*abs(x[i]-p);
    }
    return ret;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int > x(n);
    for (int i = 0; i < n; ++i)
        cin >> x[i];
    
    int l_ = *min_element(x.begin(),x.end());
    int r_ = *max_element(x.begin(),x.end());
    //int p = (r_-l_ & 1 ? r_-l_-1 : r_-l_);
    //int p_opt = p;
    int p = l_;
    vector<int> v;
    for (p; p <= r_; ++p) {
        v.emplace_back(dist(p,x));
    }
    cout << *min_element(v.begin(),v.end()) << "\n";
}


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

using namespace std;

typedef long long int64;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef complex<int64> point;
typedef vector<point> polygon;

int64 dot(point a, point b) { return real(conj(a) * b); }

int64 cross(point a, point b) { return imag(conj(a) * b); }

int64 area2(point a, point b, point c) { return cross(b - a, c - a); }

namespace std
{
	bool operator<(point a, point b)
	{
		if (a.real() != b.real())
			return a.real() < b.real();
		return a.imag() < b.imag();
	}
}

polygon convex_hull(vector<point> &P)
{
	int n = P.size(), k = 0;
	vector<point> h(2 * n);
	sort(P.begin(), P.end());
	for (int i = 0; i < n; h[k++] = P[i++])
		while (k >= 2 && area2(h[k - 2], h[k - 1], P[i]) < 0) --k;
	for (int i = n - 2, t = k + 1; i >= 0; h[k++] = P[i--])
		while (k >= t && area2(h[k - 2], h[k - 1], P[i]) < 0) --k;
	return polygon(h.begin(), h.begin() + k - (k > 1));
}


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

	int n; cin >> n;
	polygon v(n);
	for (int i = 0; i < n; ++i){
		int64 x, y; cin >> x >> y;
		v[i] = point(x, y);
	}

	polygon ch = convex_hull(v);
	int idx = 0;
	n = (int)ch.size();
	for (int i = 0; i < n; ++i){
		if (ch[i].imag() < ch[idx].imag()) idx = i;
		else if (ch[i].imag() == ch[idx].imag() && ch[i].real() < ch[idx].real()) idx = i;
	}
	cout << n << endl;
	for (int i = 0; i < n; ++i){
		point cur = ch[(i + idx) % n];
		cout << cur.real() << " " << cur.imag() << endl;
	}

	return 0;
}

Measured memory_bytes: 5944
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		String line = sc.nextLine();
		char[] tr = line.toCharArray();
		
		if(tr.length == 1) {
			System.out.println(0);
			System.exit(0);
		}
		
		//先頭を変換しないパターン
		int cnt1 = solNoRev(tr);
		//先頭を変換するパターン
		int cnt2 = solRev(tr);

		System.out.println(Math.min(cnt1, cnt2));
		
	}
	
	static private char rev(char c) {
		if(c == '1') {
			return '0';
		} else {
			return '1';
		}
	}
	
	static private int solNoRev(char[] tr) {
		char ptr = tr[0];
		int cnt = 0;
		for(int i=1; i<tr.length; i++) {
			if(ptr == tr[i]) {
				ptr = rev(tr[i]);
				cnt ++;
			} else {
				ptr = tr[i];
			}
		}
		return cnt;
	}

	static private int solRev(char[] tr) {
		char ptr = rev(tr[0]);
		int cnt = 1;
		for(int i=1; i<tr.length; i++) {
			if(ptr == tr[i]) {
				ptr = rev(tr[i]);
				cnt ++;
			} else {
				ptr = tr[i];
			}
		}
		return cnt;
	}
}

Measured memory_bytes: 26564
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <functional>
#define REP(i, n) for(int i=0;i<n;++i)
#define INF 100000000

using namespace std;

typedef pair<int, int> P;

int h, w, num;
string s;
char maze[50][50];
int d[50][50];

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

int solve(){
  queue<P> que;
  REP(i, h) REP(j, w) d[i][j] = INF;
  que.push(P(0, 0));
  d[0][0] = 0;

  while(que.size()){
    P p = que.front();
    que.pop();
    if(p.first == h-1 && p.second == w-1) break;
    ;
    REP(i, 4){
      int ny = p.first + dy[i];
      int nx = p.second + dx[i];
      if(0 <= ny && ny < h && 0 <= nx && nx < w
	 && maze[ny][nx] != '#' && d[ny][nx] == INF){
	que.push(P(ny, nx));
	d[ny][nx] = d[p.first][p.second] + 1;
      }
    }
  }

  return d[h-1][w-1];
}

int main(){
  cin >> h >> w;
  REP(i, h){
    cin >> s;
    REP(j, w){
      if(s[j] == '.') ++num;
      maze[i][j] = s[j];
    }
  }

  if(solve() == INF){
    cout << "-1" << endl;
  }
  else{
    cout << num - solve() -1 << endl;
  }

  return 0;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e14;
const int ZERO = 0;
const int MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<int,int> P;

signed main() {
    string S;
    cin >> S;
    if(S == "SUN") {
        cout << 7 << endl;
    }
    else if(S == "MON") {
        cout << 6 << endl;
    }
    else if(S == "TUE") {
        cout << 5 << endl;
    }
    else if(S == "WED") {
        cout << 4 << endl;
    }
    else if(S == "THU") {
        cout << 3 << endl;
    }
    else if(S == "FRI") {
        cout << 2 << endl;
    }
    else {
        cout << 1 << endl;
    }
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

def sol():
    N,M = list(map(int,input().split()))
    A = list(map(int,input().split()))
    tmp = sorted([list(map(int,input().split())) for _ in range(M)],key = lambda x:-x[1])

    t = []
    for a,b in tmp:
        t+=[b]*a
        
        if len(t) >=N:
            break

    A += t
    A.sort(reverse = 1)
    print(sum(A[:N]))

if __name__ == '__main__':
    sol()


Measured memory_bytes: 36820
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <numeric>
#include <array>
#include <cmath>
#include <memory>
using namespace std;
//変数デバッグ
#define DEB(variable) cout << #variable << '=' << variable << endl

//for簡易表記(引数ミス防止)
#define FOR(LoopVariable,numberOFbegin,numberOFend) for (int LoopVariable = (numberOFbegin); (LoopVariable) < (numberOFend); (LoopVariable)++)
#define DEFOR(LoopVariable,numberOFbegin,numberOFend) for (int LoopVariable = (numberOFbegin)-1; (LoopVariable) >= (numberOFend); (LoopVariable)--)
#define REP(LoopVariable,numberOFend) for(int LoopVariable = 0;(LoopVariable)<(numberOFend);LoopVariable++)

constexpr long long int linf = numeric_limits<long long int>::max()-5;
constexpr int inf= numeric_limits<int>::max()-5;
constexpr long long int mod = 1000000007;

int main(){

    int a,b;
    cin>>a>>b;
    cout<<10*(a>=b)+0*(a<b)<<endl;

    return 0;
}


Measured memory_bytes: 256
def main():
    mod = 1000000007
    N, M, *A = map(int, open(0).read().split())
    A = set(A)
    F = [0] * (N + 1)
    F[0] = 1
    if 1 not in A:
        F[1] = 1
    for i in range(2, N + 1):
        if i not in A:
            F[i] = (F[i-1] + F[i-2]) % mod
    print(F[N])


if __name__ == "__main__":
    main()


Measured memory_bytes: 14180
#!/usr/bin/env python3
import fractions

N = int(input())
a_list = list(map(int, input().split()))
x = a_list[0]
for i in range(1, N):
    x = x * a_list[i] // fractions.gcd(x, a_list[i])
mod = 10 ** 9 + 7
t = 0
for a in a_list:
    b = x // a
    t += b

ans = t % mod
print(ans)


Measured memory_bytes: 6072
package main

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

var scanner = bufio.NewScanner(os.Stdin)

func nextLine() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	i, e := strconv.Atoi(nextLine())
	if e != nil {
		panic(e)
	}
	return i
}

// for large string > 64*1024
var reader = bufio.NewReaderSize(os.Stdin, 1000000)

func readLine() string {
	buf := make([]byte, 0, 1000000)
	for {
		l, p, e := reader.ReadLine()
		if e != nil {
			panic(e)
		}
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}


func min(nums ...int) int {
    if len(nums) == 0 {
        panic("funciton min() requires at least one argument.")
    }
    res := nums[0]
    for i := 0; i < len(nums); i++ {
        res = int(math.Min(float64(res), float64(nums[i])))
    }
    return res
}

func max(nums ...int) int {
    if len(nums) == 0 {
        panic("funciton max() requires at least one argument.")
    }
    res := nums[0]
    for i := 0; i < len(nums); i++ {
        res = int(math.Max(float64(res), float64(nums[i])))
    }
    return res
}


func main() {
	scanner.Split(bufio.ScanWords) // switch to separating by space
	window := nextInt()
	curtain := nextInt()

	var answer int
	answer = max(window-curtain*2, 0)

	fmt.Println(answer)
}


Measured memory_bytes: 640
N = int(input())
A = [0] * N
for i in range(N):
  A[i] = int(input())
  
A_Max = sorted(A)[-1]
A_2nd = sorted(A)[-2]

for i in range(N):
  if A[i] == A_Max:
    print(A_2nd)
  else:
    print(A_Max)

Measured memory_bytes: 14664
fn main() {
    let _: String = read();
    let s: String = read();
    let s: Vec<char> = s.chars().collect();
    let s = s[0];
    println!("A{}C", s);
}

// 以下関数

use std::io::*;
use std::str::FromStr;
pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

pub const MOD: u64 = 1_000_000_007;

pub fn is_prime(n: i32) -> bool {
    if n < 2 {
        return false;
    } else if n == 2 {
        return true;
    }
    let mut i = 2;
    while i * i < n {
        if n % i == 0 {
            return false;
        } else {
            i += 1;
            continue;
        }
    }
    true
}

pub fn lcm(mut n: i32, mut m: i32) -> i32 {
    n = if n > m { m } else { n };
    m = if n > m { n } else { m };
    let mut i = n;
    while i % m != 0 {
        i += n;
    }
    i
}

pub fn abs(n: i32) -> i32 {
    if n >= 0 {
        n
    } else {
        -n
    }
}

pub fn max(n: i32, m: i32) -> i32 {
    if n >= m {
        n
    } else {
        m
    }
}

pub fn min(n: i32, m: i32) -> i32 {
    if n <= m {
        n
    } else {
        m
    }
}

pub fn factorial(n: u32) -> u32 {
    if n == 0 {
        return 1;
    }
    let mut r = n;
    for i in 0..n - 1 {
        r *= n - i - 1;
    }
    r
}

pub fn combination(n: u32, m: u32) -> u32 {
    factorial(n) / factorial(m) / factorial(n - m)
}


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

using namespace std;

#define MAX_N 2000
#define MAX_C 2000

typedef long long ll;

ll C, N;

ll v[MAX_N], w[MAX_N];

ll dp[MAX_N+1][MAX_C+1];

void solve()
{

    for(ll i = 0; i < N; i++)
    {
        for(ll j = C; j >= 1; j--)
        {
            
            if(j < w[i])
            {
                dp[i+1][j] = dp[i][j];
            } else {
                if(dp[i][j] >= dp[i][j-w[i]] + v[i])
                {
                    dp[i+1][j] = dp[i][j];
                } else {
                    dp[i+1][j] = dp[i][j-w[i]] + v[i];
                }
            }
        }
    }

    cout << dp[N][C] << '\n';

}

int main() {

    cin >> N >> C;
    
    for(ll i = 0; i < N; i++)
        cin >> w[i] >> v[i];

    solve();

    return 0;
}

Measured memory_bytes: 5964
fun main(args: Array<String>) {
    val (H, W, K) = readInputLine().split(" ").map { it.toInt() }
    val cake = Array(H) { readInputLine().toCharArray() }
    val containsStrawberry = BooleanArray(H) { cake[it].contains('#') }
    
    val ans = Array(H) { IntArray(W) }

    var now = 1
    var cakeDetected = false

    for (i in 0 until H) {
        if (!containsStrawberry[i]) {
            continue
        }
        cakeDetected = false
        for (j in 0 until W) {
            if (cake[i][j] == '#') {
                if (!cakeDetected) {
                    cakeDetected = true
                } else {
                    now++
                }
            }
            ans[i][j] = now
        }
        now++
    }
    
    var topDetected = false
    
    for (i in 0 until H) {
        if (containsStrawberry[i]) {
            if (!topDetected) {
                topDetected = true
                for (j in 0 until i) {
                    ans[j] = ans[i].copyOf()
                }
            }
        } else {
            if (topDetected) {
                ans[i] = ans[i - 1].copyOf()
            }
        }
    }

    for (a in ans) {
        println(a.joinToString(" "))
    }
}

fun readInputLine(): String {
    return readLine()!!
}


Measured memory_bytes: 40528
n, k = map(int, input().split())
d = [0] * k
sunuke = {}
for i in range(n):
    sunuke.setdefault(str(i),0)
for i in range(n):
    sunuke[str(i)] = 0

for i in range(k):
    d[i] = int(input())
    A = list(map(int, input().split()))
    for j in range(d[i]):
        sunuke[str(A[j]-1)] += 1
ans = list(sunuke.values()).count(0)
print(ans)





Measured memory_bytes: 9120
N, M = [int(x) for x in input().split()]
X = sorted([int(x) for x in input().split()])
D = []
for i in range(len(X)-1):
    D.append(X[i+1] - X[i])
if (N == 1):
    print(sum(D))
else:
    print(sum(sorted(D)[:(-N+1)]))



Measured memory_bytes: 58536
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <random>
#include <chrono>
#include <queue>
#include <math.h>
#include <string>
#include <sstream>
#include <stack>
#define inf 1e9+7
#define pb push_back
#define make make_pair
 
using namespace std;
 
#define ll long long
#define rep(i,n) for(ll i=0;i<n;i++)
#define PI 3.14159265359
long long gcd(long long a,long long b){ return b==0?a:gcd(b,a%b);}
long long lcm(long long a,long long b){ return a/gcd(a,b)*b;}


int main(){
    ll a,b,c;
    cin >> a >> b >> c;
    if(c-a-b>=0){
        if(4*a*b<(c-a-b)*(c-a-b)) cout <<"Yes" << endl;
        else cout << "No" << endl;
    }
    else{
         cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
template <typename Q_type>
using smaller_queue = priority_queue<Q_type, vector<Q_type>, greater<Q_type>>;

constexpr int MOD_TYPE = 1;
constexpr ll MOD = (MOD_TYPE == 1 ? (ll)(1e9 + 7) : 998244353);
constexpr int INF = (int)1e9;
constexpr ll LINF = (ll)4e18;
constexpr ld PI = acos(-1.0);
constexpr ld EPS = 1e-11;
constexpr int Dx[] = {0, 0, -1, 1, -1, 1, -1, 1, 0};
constexpr int Dy[] = {1, -1, 0, 0, -1, -1, 1, 1, 0};

#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << "\n"
#define Yes(n) cout << ((n) ? "Yes" : "No") << "\n"
#define possible(n) cout << ((n) ? "possible" : "impossible") << "\n"
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << "\n"
#define Yay(n) cout << ((n) ? "Yay!" : ":(") << "\n"
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << "\n";

#pragma endregion

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(30) << setiosflags(ios::fixed);
  int h, w;
  cin >> h >> w;
  rep(i, w + 2) cout << "#";
  cout << endl;
  rep(i, h)
  {
    cout << "#";
    string s;
    cin >> s;
    cout << s;
    cout << "#";
    cout << endl;
  }
  rep(i, w + 2) cout << "#";
  cout << endl;
  return 0;
}

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

int main() {
  int N, C, K;
  cin >> N >> C >> K;
  vector<int> T(N);
  for (int i = 0; i < N; i++) cin >> T.at(i);

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

  int lim = T.at(0) + K, c = 0, ans = 1;
  for (int i = 0; i < N; i++) {
    if (T.at(i) <= lim && c < C) c++;
    else lim = T.at(i) + K, c = 1, ans++;
  }
  cout << ans << "\n";
}

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


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

if(a > b){
  cout << a + (a - 1) << endl;
}else if (a == b){
  cout << b + b << endl;
} else{
  cout << b + (b - 1) << endl;
}
}

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

int main()
{
  while (true)
  {
    i64 n;
    cin >> n;
    if (n == 0)
      break;
    vector<i64> a(n);
    i64 sum = 0;
    for (i64 i = 0; i < n; i++)
    {
      cin >> a[i];
      sum += a[i];
    }
    i64 ans = 0;
    for (i64 i = 0; i < n; i++)
      if (a[i] <= sum / n)
        ans++;
    cout << ans << endl;
  }
  return 0;
}



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

using namespace std;

int main()
{
	int n;
	cin >> n;
	for(int D = 0; D < n; ++D){
		string s;
		cin>>s;
		
		if(s.compare(0,2,">'")== 0){
			int bef_eq = 0;
			int aft_eq = 0;
			int shp = 0;
			int pos_shp = 0;
			int pos_tld = 0;

			for(unsigned int i = 2; i < s.length(); ++i ){
				if( s[i] == '=' )
					if( shp == 0 )
						++bef_eq;
					else
						++aft_eq;
				else if( s[i] == '#' ){
					shp++;
				}else if( s[i] == '~' ){
					pos_tld = i;
					break;
				}else{
					shp = 2;
					break;
				}
			}
			if( bef_eq && aft_eq && pos_tld && bef_eq == aft_eq &&
				shp == 1 && pos_tld == s.length() - 1 )
				cout << "A\n";
			else
				cout << "NA\n";
		}else if(s.compare(0,2,">^")==0){
			int cnt_qeq = 0;
			int pos_tltl = 0;
			bool invalid = false;
			
			if( s.length() <= 2 || s.length() % 2 == 1 )
				invalid = true;
			
			for(unsigned int i = 2; i < s.length() && !invalid; i+=2){
				if( s.compare(i,2,"Q=") == 0 )
					++cnt_qeq;
				else if( s.compare(i,2,"~~") == 0 ){
					pos_tltl = i;
					break;
				}else
					invalid = true;
			}
			if( cnt_qeq == 0 || pos_tltl != s.length() - 2 ){
				invalid = true;
			}
			if( invalid )
				cout << "NA\n";
			else
				cout << "B\n";
		}else{
			cout <<"NA\n";
		}
	}
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<utility>
#include<algorithm>
using namespace std;
#define ll int64_t
#define REP(i, n) for (int i=0; i<n; i++)

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

    ll N, M, R;
    cin >> N >> M >> R;
    vector<ll> r(R), A(M), B(M), C(M);
    vector<vector<ll>> D(N, vector<ll>(N, 100000000000));

    REP(i, R){
        cin >> r[i];
        r[i]--;
    }
    REP(i, M){
        cin >> A[i] >> B[i] >> C[i];
        A[i]--;
        B[i]--;
    }

    REP(i, M){
        D[A[i]][B[i]] = C[i];
        D[B[i]][A[i]] = C[i];
    }

    //Warshall-Floyd Algorithm
    REP(i, N){
        REP(j, N){
            REP(k, N){
                if (D[j][k] > D[j][i] + D[i][k]){
                    D[j][k] = D[j][i] + D[i][k];
                } 
            }
        }
    }

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

    ll ans = 100000000000000;

    do{
        ll temp = 0;
        REP(i, R-1){
            temp += D[r[i]][r[i+1]];
        }
        ans = min(ans, temp);
    }while(next_permutation(r.begin(), r.end()));

    cout << ans << "\n";

}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
template<typename T> void read(T &num){
	char c=getchar();T f=1;num=0;
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){num=(num<<3)+(num<<1)+(c^48);c=getchar();}
	num*=f;
}
template<typename T> void qwq(T x){
	if(x>9)qwq(x/10);
	putchar(x%10+'0');
}
template<typename T> void write(T x){
	if(x<0){x=-x;putchar('-');}
	qwq(x);putchar('\n');
}
int num[2010];

int main(){
	int n,x,y;read(n);read(x);read(y);
	rep(i,1,n){
		rep(j,i+1,n){
			int dis=0;
			if(i<x){
				if(j<x){dis=j-i;}
				else if(x<=j&&j<=y){dis=x-i+min(j-x,y-j+1);}
				else{dis=j-y+x-i+1;}
			}else if(x<=i&&i<=y){
				if(x<=j&&j<=y){dis=min(j-i,y-j+i-x+1);}
				else{dis=j-y+min(y-i,i-x+1);}
			}else{dis=j-i;}
			num[dis]++;
		}
	}
	rep(i,1,n-1)write(num[i]);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define pb push_back
#define pii pair<long long,long long>
#define endl '\n'
#define N 300001
int mod=1000000007;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
vector<int> parent(N),sz(N),indegree(N),vis(N); char st[N];
vector<int> adj[N];
int modexp(int x,int n,int M)
{
    if(n==0)
        return 1;
    else if(n%2 == 0)        
        return modexp((x*x)%M,n/2,M);
    else                             
        return (x*modexp((x*x)%M,(n-1)/2,M))%M;
}
void make_set(int s)
{
    parent[s]=s;
    sz[s]=1;
}
int find_parent(int p)
{
    if(p==parent[p])
    return p;
    return parent[p]=find_parent(parent[p]);
}
void union_set(int a,int b)
{
    a=find_parent(a);b=find_parent(b);
    if(a!=b)
    {
        if(a<b)
        swap(a,b);
        parent[b]=parent[a];
        sz[a]+=sz[b];
    }
}
void solve()
{
    int n,k; cin>>n>>k;
    vector<int>v;
    v.resize(n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    vector<int> dp(n+1);
    dp[2]=abs(v[2]-v[1]);
    for(int i=3;i<=n;i++)
    {
        int val=INT_MAX;
        for(int j=1;j<=k;j++)
        {
            if(i-j>=1)
            val=min(val,dp[i-j]+abs(v[i]-v[i-j]));
        }
        dp[i]=val;
    }
    cout<<dp[n];
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int test; test=1;
    while(test--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 18304
#include <bits/stdc++.h>
	
#define all(a) a.begin(), a.end()
#define allr(a) a.rbegin(), a.rend()
#define rev(v) reverse(v.begin(), v.end());
#define io() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); srand(time(NULL));
	
using namespace std;
	
using ll = long long;
using ld = long double;
using ull = unsigned long long;
	
signed main(){
	io();
	ll n, k; cin >> n >> k;
	vector<ll> v(n), cost(n, 1e9 + 1);
	cost[0] = 0;
	for(auto &x : v) cin >> x;
	for(ll i = 0; i < n; ++i){
		for(ll j = 0; j <= k; ++j){
			if(i - j >= 0){
				cost[i] = min(abs(v[i] - v[i - j]) + cost[i - j], cost[i]);
			}
		}
	}
	return cout << cost[n - 1] << '\n', 0;
}

Measured memory_bytes: 4780
#include<stdio.h>
using namespace std;
int main()
{
    char a, b;
    scanf("%c %c", &a, &b);
    if(a=='H' || a=='D'){
            if(b=='H' || b=='D'){
        if(a==b){
            printf("H\n");
        }
        else{
            printf("D\n");
        }
    }
    }
   return 0;
}

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

namespace TYC
{
	typedef long long ll;
	const int N = 2e5 + 5;

	int n, Fa[N], C[N][2], bel[N];
	struct data
	{
		int p, c0, c1;
		bool operator < (const data &t) const { return (ll)c0 * t.c1 < (ll)t.c0 * c1; }
	};
	priority_queue<data> Q;

	inline int read()
	{
		int x = 0, f = 0, ch = getchar();
		while (!isdigit(ch))
			f |= (ch == '-'), ch = getchar();
		while (isdigit(ch))
			x = x * 10 + ch - '0', ch = getchar();
		return f ? -x : x;
	}

	int find(const int x) { return bel[x] == x ? x : bel[x] = find(bel[x]); }

	void work()
	{
		n = read();
		for (int i = 2; i <= n; i++)
			Fa[i] = read();
		for (int i = 1; i <= n; i++)
		{
			C[i][read()] = 1, bel[i] = i;
			if (i != 1)
				Q.push({i, C[i][0], C[i][1]});
		}
		ll ans = 0;
		data v;
		for (int k = 1; k < n; k++)
		{
			do
			{
				v = Q.top();
				Q.pop();
			}
			while (v.c0 != C[v.p][0] || v.c1 != C[v.p][1]);
			int p = v.p, f = find(Fa[p]);
			ans += (ll)C[f][1] * C[p][0];
			C[f][0] += C[p][0];
			C[f][1] += C[p][1];
			bel[p] = f;
			if (f != 1)
				Q.push({f, C[f][0], C[f][1]});
		}
		printf("%lld\n", ans);
	}
}

int main()
{
	TYC::work();
	return 0;
}

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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()

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

  ll N,W;
  cin>>N>>W;
  vector<ll>w(N),v(N);
  for(int i=0;i<N;i++)cin>>w[i]>>v[i];
  vector<vector<ll>>dp(N+1,vector<ll>(W+1,0));
  for(int i=1;i<=N;i++){
    for(int j=0;j<=W;j++){
      if(j-w[i-1]>=0)dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);
      else dp[i][j]=dp[i-1][j];
    }
  }
  ll ans=0;
  for(int i=0;i<=W;i++){
    ans=max(ans,dp[N][i]);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 80256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, m, n) for(int i = (m); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1e9)
#define PI (acos(-1))
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl


int main() {
    int n;  cin >> n;
    vector<int> v(n);
    rep(i, n)  cin >> v[i];

    vector<int> even;
    vector<int> odd;
    rep(i, n) {
        if (i % 2 == 0) even.push_back(v[i]);
        else odd.push_back(v[i]);
    }

    vector<int> e(100000);
    vector<int> o(100000);
    rep(i, n/2) {
        e[even[i]]++;
        o[odd[i]]++;
    }
    pair<int, int> pe[100000];
    pair<int, int> po[100000];
    rep(i, 100000) {
        pe[i] = make_pair(e[i], i);
        po[i] = make_pair(o[i], i);
    }
    sort(pe, pe+100000);
    reverse(pe, pe+100000);
    sort(po, po+100000);
    reverse(po, po+100000);

    sort(all(e), greater<int>());
    sort(all(o), greater<int>());

    if (pe[0].second == po[0].second) {
        print(min(n-e[0]-o[1], n-e[1]-o[0]));
    } else {
        print(n - e[0] - o[0]);
    }
}


Measured memory_bytes: 3580
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
#include<stdio.h>
#include <cstdint>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define RNG(x, a, n) &((x)[a]), &((x)[n])
typedef pair<int, int> PII;
typedef long long ll;
template<typename T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
template<typename T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
const int inf = 1e9 + 7;
const ll longinf = 1LL << 60;
const ll mod = 1e9 + 7;

int k, x;

int main() {

	cin >> k >> x;

	if (x <= k * 500)cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdlib>
#include<queue>
#include<set>
#include<cstdio>
#include<map>

using namespace std;

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

typedef vector<int> vec;
typedef vector<vec> mat;

const ll mod = 1000000007;
const int INF = 1<<30;

int main() {
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    vector<int> dp(n+1, INF);
    dp[n] = 0;
    queue<int> q;
    q.push(0);
    for (int i = n-1; i >= 0; i--) {
        while(1){
            if(q.size() == 0){
                puts("-1");
                return 0;
            }
            if (q.front() != INF && q.size() <= m) break;
            q.pop();
        }
        if (s[i] == '0') dp[i] = q.front()+1;
        q.push(dp[i]);
    }
    
    vector<int> ans;
    int x = 0;
    int rest = dp[0];
    while(x < n){
        --rest;
        int i = 1;
        while(dp[x+i] != rest) i++;
        ans.push_back(i);
        x += i;
    }
    rep(i, ans.size()){
        printf("%d%c", ans[i], i==int(ans.size())-1?'\n':' ');
    }
}

Measured memory_bytes: 4272
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

int main()
{
	ll N;
	cin >> N;
	ll tmp = N;
	ll ans = INF;
	for (ll i = 1; i * i <= N; i++) {
		if (tmp % i == 0) ans = min(ans, i + N / i - 2);
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
 using namespace std;
int main(){
  int N;
  cin >>N;
  int ans;
  ans = 0;
  int AK[1000001];
  for(int i=0;i<1000001;i++){
    AK[i]=0;
  }
  for(int i=1;i<=100;i++){
    for(int j=1;j<=100;j++){
      for(int k=1;k<=100;k++){
        AK[i*i+j*j+k*k+i*k+j*k+i*j]++;
      }
    }
  }
  for(int i=1;i<=N;i++){
  cout << AK[i] <<endl;
  }
}

Measured memory_bytes: 7320
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){

    
    int x1,x2,y1,y2;
    cin>>x1>>y1>>x2>>y2;
    
    int a=x2-x1;
    int b=y2-y1;
    int x3,y3,x4,y4;
    x3=x2-b;
    y3=y2+a;
    x4=x3-a;
    y4=y3-b;
    cout<<x3<<" "<<y3<<endl;
    cout<<x4<<" "<<y4<<endl;
    
    

return 0;
}


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

int main() {
  int N;
  cin >> N;
  
  vector<int> v(N);
  for (int i = 0; i < N; i++) {
    cin >> v.at(i);
  }
  
  int cnt = 0;
  for (int i = 0; ; ) {
    if (i == 1) {
      cout << cnt << endl;
      return 0;
    } else {
      i = v.at(i) - 1;
      cnt++;
      if (cnt > N) {
        cout << -1 << endl;
        return 0;
      }
    }
  }
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main (){
    set<int>T;
int p,q,r;
cin>>p>>q>>r;
int w=p+q;
int e=r+q;
int t=p+r;
T.insert(w);
T.insert(e);
T.insert(t);
cout<<*T.begin();
return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
int main(){
  ll t,y;
  cin >> t >> y;
  ll k = 0;
  k = t * y;
  if(t == 1 || y == 1){
    cout << 1 << endl;
  }
  else if(k % 2 == 0){
    cout << k / 2 << endl;
  }
  else{
    cout << k / 2 + 1 << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define int ll
#define pb push_back
#define setbits(x)          __builtin_popcountll(x)
#define endl "\n"
typedef long long ll;
int decimalsum(int x){
int sum=0;
while(x){
    sum+=x%10;
    x=x/10;
}
return sum;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//                int php[4000] , cdc[8000], cdm[8000];
//                for(int j=0;j<5;j++){
//for(int i=0;i<2000;i++)php[i/10]=1;
//for(int i=0;i<2000;i++)php[i/10]=1;
//for(int i=0;i<2000;i++)php[i/10]=1;
//for(int i=0;i<2000;i++)php[i/10]=1;
//for(int i=0;i<2000;i++)php[i/10]=1;
//for(int i=0;i<2000;i++)php[i/10]=1;
//
//int t;
//cin>>t;
//while(t--)
{
   //solve();
  int n , k;
  cin>>n>>k;
  vector<int>a(n+1);
  for(int i=1;i<=n;i++)cin>>a[i];
  vector<int>dp(n+1 , 0);
  dp[2]=abs(a[1]-a[2]);
  for(int i=3;i<=n;i++){
        dp[i]=INT_MAX;
        for(int j=1;j<=k;j++){
            if(i-j<1)break;
    dp[i]= min(abs(a[i]-a[i-j]) +dp[i-j],dp[i]);
        }
  }
  cout<<dp[n]<<endl;

}
    return 0;
}


Measured memory_bytes: 4780
def main():
    n, k, q = map(int, input().split())
    a_list = [0 for _ in range(n)]

    for _ in range(q):
        a = int(input())
        a_list[a - 1] += 1

    if k > q:
        for _ in range(n):
            print("Yes")
        exit()

    for a in a_list:
        if a < q - k + 1:
            print("No")
        else:
            print("Yes")


if __name__ == "__main__":
    main()


Measured memory_bytes: 79948
n,m=map(int,input().split())
seq=[]
for i in range(n):
    seq.append(0)
s=[]
c=[]
for i in range(m):
    a,b=map(int,input().split())
    s.append(a)
    c.append(b)
check=0
for i in range(m):
    for j in range(i+1,m):
        if s[i]==s[j] and c[i]!=c[j]:
            check+=1
for i in range (m):
    if s[i]==1 and c[i]==0 and n!=1:
        check+=1
if check>0:
    print(-1)
else:
    for i in range(m):
        seq[s[i]-1]=c[i]
    if seq[0]==0 and n!=1:
        seq[0]=1
    num=0
    for i in range(n):
        num+=seq[i]*(10**(n-1-i))
    print(num)

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
	  Scanner sc = new Scanner(System.in);
	  int n=sc.nextInt();
	  int[] a=new int[4];
	  for(int i=0;i<n;i++) {
		  String buff=sc.next();
		  if(buff.equals("AC")) {
			  a[0]++;
		  }else if(buff.equals("WA")) {
			  a[1]++;
		  }else if(buff.equals("TLE")) {
			  a[2]++;
		  }else {
			  a[3]++;
		  }
	  }
	  System.out.println("AC x "+a[0]);
	  System.out.println("WA x "+a[1]);
	  System.out.println("TLE x "+a[2]);
	  System.out.println("RE x "+a[3]);
  }
}


Measured memory_bytes: 58500
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,b=0;
  cin >>N;
  vector<int> A(N,0);
  for(int i=0; i<N; i++){
    int a;
    cin >>a;
    a-=i;
    A[i]=a;
    b=max(b,a);
  }
  int h=b, l=-1e9, mid=(h+l)/2;
  while(h-l>1){
    int plus=0, zero=0, minus=0;
    for(int i=0; i<N; i++){
      if(A[i]-mid>0) plus++;
      if(A[i]-mid==0) zero++;
      if(A[i]-mid<0) minus++;      
    }
    if(plus>(zero+minus)) l=mid;
    else if(minus>(zero+plus)) h=mid;
    else{
      h=mid;
      break;
    }
    mid=(h+l)/2;
  }
  long long ans=0,temp=0;
  for(int i=0; i<N; i++){
    ans+=abs(A[i]-h);
    temp+=abs(A[i]-l);
  }
  ans=min(ans,temp);
  cout <<ans <<endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
#include <map>
#include <cstdlib>
#include <sstream>
#include <bitset>
using namespace std;

typedef long long ll;

ll mod=ll(1e9)+7;

int main()
{
    string L;
    cin >> L;
    int len=L.size();
    ll dp1[len+1];//A,Bの上からk桁目まで確定させ和がL以下であることがわかっているもの
    ll dp2[len+1];//A,Bの上からk桁目まで確定させ和がL以下であることがわかっていないもの
    dp1[1]=1;
    dp2[1]=2;
    for(int i=2; i<=len; i++){
        if(L[i-1]=='1'){
            dp1[i]=(dp1[i-1]*3+dp2[i-1])%mod;
            dp2[i]=dp2[i-1]*2%mod;
        }else{
            dp1[i]=dp1[i-1]*3%mod;
            dp2[i]=dp2[i-1];
        }
    }

    cout << (dp1[len]+dp2[len])%mod << endl;
    
    return 0;
}

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

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

typedef long long ll;

const char nl = '\n' ;
const ll MOD = 1e9 + 7;


int main()
{
   ios_base::sync_with_stdio(0); cin.tie(0);
   int n; cin >> n;
   int x = pow(n, 0.5);
   cout << x*x << nl;

   return 0;


}


Measured memory_bytes: 3992
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

void main() {
    readint;
    auto a = readints;

    int ans = a.map!(e => e - 1).sum;
    writeln(ans);
}


Measured memory_bytes: 380
#include<iostream>
#include<iomanip>


using namespace std;

int main(){
  int N;
  cin >> N;
  double fizz = 3;
  double buzz = 5;
  int fizzbuzz = 15;
  double fizzsum = 0;
  double buzzsum = 0;
  double fizzbuzzsum =0;
  int fizzstate = N/fizz;
  int buzzstate = N/buzz;
  int fizzbuzzstate = N/fizzbuzz;
  long ans;

  for(int i=1;i<=N;i++){
    ans +=i;
  }


  for(int i=1;i<=buzzstate;i++){
    buzzsum += buzz*i;
  }
  for(int i=1;i<=fizzstate;i++){
    fizzsum += fizz*i;
  }
  for(int i=1;i<=fizzbuzzstate;i++){
    fizzbuzzsum += fizzbuzz*i;
  }
  if(N==0){
    cout << 0 << endl;
    return 0;
  }
  ans = ans - fizzsum - buzzsum + fizzbuzzsum;

  
  cout << ans << endl;






}

Measured memory_bytes: 3624
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int main() {
  int64_t N;
  std::cin >> N;
  std::vector<std::string> S;
  for (int64_t i = 0; i < N; ++i) {
    std::string Si;
    std::cin >> Si;
    S.push_back(Si);
  }
  std::sort(S.begin(), S.end());
  decltype(S)::iterator result = std::unique(S.begin(), S.end());
  const int64_t forprint = std::distance(S.begin(), result);
  std::cout << forprint << std::endl;
}

Measured memory_bytes: 11660
#!/usr/bin/env python
# coding: utf-8
#

import copy

def advance(h, w, nx, ny):
    if 0 == ny % 2:
        if nx == w - 1:
            return nx , ny + 1
        else:
            return nx + 1, ny
    elif 1 == ny % 2:
        if nx == 0:
            return nx, ny + 1
        else:
            return nx - 1, ny

    

def main(h, x, mat):
    nx = 0
    ny = 0
    retlist = []
    while nx < w and ny < h:
        ''' 終了条件
        '''
        next_x, next_y = advance(h, w, nx, ny)
        if next_x == w or next_y == h:
            break
        if 0 == mat[ny][nx] % 2:
            pass
        else:
            mat[ny][nx] -= 1
            mat[next_y][next_x] += 1
            retlist.append([ny, nx, next_y, next_x])
            # print('{} {} {} {}'.format(ny, nx, next_y, next_x))
        nx = next_x
        ny = next_y

        
    print(len(retlist))
    for i in range(len(retlist)):
        print('{} {} {} {}'.format(retlist[i][0] + 1, retlist[i][1] + 1, retlist[i][2] + 1, retlist[i][3] + 1))
                
    
if __name__ == '__main__':
    try:
        h, w  = list(map(int, input().strip().split(' ')))
        mat = []
        for i in range(h):
            mat.append(list(map(int, input().strip().split(' '))))
        main(h, w, mat)
    except EOFError:
        pass


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

int H, W;
int one, two;

string S[404];
int visit[404][404];

void dfs(int i, int j, char x)
{
    if(i < 0 || j < 0 || i == H || j == W || S[i][j] != x || visit[i][j])
        return;
    
    visit[i][j] = 1;
    one += (S[i][j] == '#');
    two += (S[i][j] == '.');
    
    dfs(i-1, j, (x == '#' ? '.' : '#'));
    dfs(i+1, j, (x == '#' ? '.' : '#'));
    dfs(i, j-1, (x == '#' ? '.' : '#'));
    dfs(i, j+1, (x == '#' ? '.' : '#'));
}

int main() {
    
    ios::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);
    
    cin >> H >> W;
    
    for(int i=0; i<H; i++)
        cin >> S[i];
    
    long long ans = 0;
    
    for(int i=0; i<H; i++)
    {
        for(int j=0; j<W; j++)
        {
            if(visit[i][j])
                continue;
            
            one = 0, two = 0;
            dfs(i, j, S[i][j]);
            
            ans += 1LL * one * two;
        }
    }
    
    cout << ans << "\n";
    return 0;
}

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

int main() {
  long long a, b, c, k;
  scanf("%lld %lld %lld %lld", &a, &b, &c, &k);
  k %= 2;
  while (k--)
    swap(a, b);
  printf("%lld\n", a - b);
  return 0;
}

Measured memory_bytes: 256