Bedao Grand Contest 16 - Kim cương

Xem dạng PDF
Gửi bài giải
Điểm: 0,02 (OI)
Giới hạn thời gian: 1.5s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Tác giả:
bedao
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Khoa là một kẻ cuồng với những viên đá quý, đặc biệt là kim cương. Hiện tại Khoa có một danh sách ~N~ mỏ kim cương được đặt ở đâu đó trên trục tọa độ. Khoa muốn khai thác nhiều nhất kim cương từ các mỏ đã biết trước. Phạm vi khai thác của Khoa cũng kì hoặc như cách anh ấy thích kim cương, gọi ~(u, v)~ là tâm điểm của phạm vi mà Khoa khai thác, thì Khoa sẽ khai thác được các ô ~(u - 1, v - 1)~, ~(u - 1, v)~, ~(u - 1, v + 1)~, ~(u, v - 2)~, ~(u, v - 1)~, ~(u, v)~ ~(u, v + 1)~, ~(u, v + 2)~, ~(u + 1, v - 1)~, ~(u + 1, v)~, ~(u + 1, v + 1)~, ~(u + 2, v)~.

Hình minh họa:

image

Vì toàn ngỗng trong bộ môn hình học giải tích, nên Khoa quyết định nhờ bạn giúp anh ấy thõa sức với đam mê kim cương của mình.

Input

  • Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \leq N \leq 10^5~) – Số lượng mỏ kim cương.

  • ~N~ dòng tiếp theo, mỗi dòng chứa ~3~ số nguyên ~x, y, w~ (~1 \leq x, y, w \leq 10^9~) biểu diễn một mỏ kim cương trên trục tọa độ – ~x, y~ đại diện cho tọa độ của mỏ, ~w~ là số viên kim cương trong mỏ.

Output

Một dòng duy nhất là số lượng kim cương tối đa mà Khoa có thể khai thác được.

Scoring

Subtask Điểm Giới hạn
1 ~50~ ~1 \leq x, y \leq 10^3~
2 ~50~ Không có ràng buộc gì thêm

Sample Input 1

5
1 1 5
1 2 3
1 3 9
2 3 4
2 2 4

Sample Output 1

25

Notes

Chọn tâm điểm khai thác là ~(2, 2)~, Khoa sẽ khai thác được cả ~5~ mỏ kim cương, lấy được tổng cộng ~25~ kim cương.

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    pppssslc  đã bình luận lúc 12, Tháng 5, 2025, 16:31 ← sửa 2

    spoil!!!

    Nhận xét:

    Mỗi mỏ sẽ có 12 vị trí tâm điểm khác nhau có thể khai thác được mỏ đó.

    Khi đó, ta sẽ:

    • Lưu số kim cương có thể khai thác tại mỗi tâm vào 1 map.
    • Duyệt qua từng mỏ:
    • Tại mỗi mỏ, ta duyệt hết 12 vị trí tâm đó.
    • Cộng vào mỗi vị trí tâm đó là số kim cương tại mỏ hiện tại.

    Lưu ý:

    Không dùng mảng để lưu số kim cương có thể khai thác tại mỗi mỏ vì sẽ bị tràn bộ nhớ khi x và y lên tới 1e9.

    Độ phức tạp: O(12nlogn)

    Code mẫu:

    #include<bits/stdc++.h>
#define str string
#define ll long long
#define db double
#define pii pair < int, int>
#define se second
#define fi first
#define vi vector<int>
#define vii vector<vector<int>>
#define mpii map < int, int>
#define si set<int>
using namespace std;

const int mod=1e9+7;
const int maxn=1e5+1;

vector<pii> move_={{0, 0}, {0, -1}, {0, 1}, {1, 0}, {1, 1}, {1, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {-2, 0}, {0, 2}, {0, -2}};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, ans=0; cin>>n;
    map < pii, ll> val;
    while(n--){
        int x, y; ll w; cin>>x>>y>>w; x--; y--;
        for(auto a: move_){
            int u=x+a.fi, v=y+a.se;
            if(u>=0 && v>=0){
                val[{u, v}]+=w;
                ans=max(ans, val[{u, v}]);
            }
        }
    }
    cout << ans;
    return 0;
}

  • -21
    audhid  đã bình luận lúc 16, Tháng 5, 2024, 9:48

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.